Epibiotic coccoid microfossils of probable cyanobacterial affinity were discovered in cherty stratiform stromatolites of the 1400-1500 Ma Gaoyuzhuang Formation, Hebei Province, northern China, Sessile coccoids with polarized growth settled on cyanobacterial sheaths and developed dense populations, These microfossils represent the earliest known occurrence of epibiosis in the fossil record with characteristics similar to those observed in modern aquatic environments, The reported fossil epibionts are also the first known occurrence of Proterozoic cyanobacteria of chamaesiphonalean affinity, The presence of specialized epibiotic communities in Gaoyuzhuang stromatolites demonstrates that epibiosis was well established and diversified by Mesoproterozoic time, reflecting early adaptation in response to competitive pressures for microbial attachment sites in ancient, densely populated shallow-water benthos or, possibly, the onset of specialized mutualistic relationships among cooccurring microorganisms.