It was numerically predicted that dissolved gas particles could enrich and adsorb at hydrophobic-liquid interfaces. Here we observe nucleation and growth of bright patches of similar to 0.45 nm high on the graphite surface in pure water with frequency-modulation atomic force microscopy when the dissolved gas concentration is below the saturation level. The bright patches, suspected to be caused by adsorption of nitrogen molecules at the graphite-water interface, are composed of domains of a rowlike structure with the row separation of 4.2 +/- 0.3 nm. The observation of this ordered adlayer might underline the gas segregation at various water interfaces.