The almost-pure quartz–cemented Fontainebleau Formation (Paris Basin, France) sandstones are known to preserve their porosity because of microcrystalline quartz coatings. Here, we use nuclear magnetic resonance (NMR) techniques, petrography, scanning electron microscopy, porosity and permeability measurements, hysteresis, and mercury injection capillary pressure curves to identify and analyze their porosity structure. Nuclear magnetic resonance experiments include transverse relaxation time (T2) distributions and T2-filtered T2–T2 exchange (T2F-TREx), a technique that provides estimates on the diffusion coupling by comparing the evolution of families of pores in T2 distributions at different exchange times. Samples were divided according to their texture, composition, and abundance of microcrystalline quartz crystals, comprising group 1 samples with very low amounts of coatings and group 2 samples with entire grains coated by microquartz. Both groups show three (or four) peaks in NMR 2-MHz T2 distribution at approximately 1 (peak A), 10−1 (peak B), and 10−2 s (peak C); group 2 samples present a slight shift to shorter T2 times in comparison with other samples. The longest T2 peak A is because of intergranular macropores, whereas the shortest peak C is because of the microporosity associated with the microcrystalline quartz coating at the surface of the pores. Peak B is also because of microporosity associated with microcrystalline quartz, but with a different surface/volume ratio being likely related to flat-shaped pores within the microcrystalline coating. The T2F-TREx indicates the proton exchange is higher between macropores and the pore surface micropores (peak C) than between macropores and the internal flat-shaped micropores; no exchange between the two sets of micropores can be observed. Our results show the potential of NMR techniques in characterizing the microporosity in Fontainebleau sandstones, which is key for the mechanism of porosity preservation in these rocks.