Thick laminar to columnar stromatolitic growths encrust typical high-energy coralgal reef communities in a French Polynesian outer-reef edge. The reef communities accumulated during vertical growth from 5870 ±100 yr B.P. to the present, at depths never exceeding 5 m below mean sea level. Oxygen and carbon isotope records and high calcification rates of stromatolite-encrusted corals strongly suggest that for about the past 6000 yr, the local environmental conditions were optimal for reef development. Accordingly, stromatolites can grow in healthy Holocene reefs. Because similar stromatolites have been recorded in other Cenozoic reefs, we suggest that microbial structures may have played a more prominent role in Cenozoic reef growth than is currently recognized.