Air-cleaved mica surfaces exhibit a high density of nanometer or micrometer size particles that have been ascribed to potassium carbonate formed as it reaction product of carbonaceous gases with potassium ions. Unambiguous evidence for this assignment has, however, never been presented. We study air-cleaved mica surfaces by high-resolution noncontact atomic force microscopy (NC-AFM) in ultrahigh vacuum to reveal the detailed structure of such precipitates on the surface. Among a large number of irregularly shaped surface structures, we find flat, hexagonally shaped islands exhibiting two different patterns on their surfaces, namely a rectangular atomic corrugation pattern and a hexagonal moire Structure. The unit cell of the rectangular pattern corresponds to the dimensions of the potassium carbonate bulk structure and is found on high crystallites. The moire structure solely appears on very flat islands and is caused by the interference of the potassium carbonate lattice periodicity and the lattice periodicity of the underlying mica substrate. Both results strongly point to the presence of potassium carbonate crystallites on air-cleaved mica surfaces.