We report the potentials of nanometer-sized contrast agents which are called gas vesicles (GVs) for super-resolution ultrasound (SRUS) imaging to diagnose of vasculature deep inside tissue. Thus, we developed the GVs and ultrasound localization microscopy (ULM) based on singular value decomposition and 2D cross-correlation techniques. Furthermore, the SRUS imaging of the vessel-mimicking phantom with the GVs was performed. These results demonstrate that GVs could have potentials as novel contrast agents at nanoscale for implementing the SRUS imaging, thus indicating that ULM with GVs would be used for better visualization of micro-vasculature in vivo.