Marine phosphate-rich sedimentary deposits (phosphorites) are important geological reservoirs for the biologically essential nutrient phosphorous. Phosphorites first appear in abundance approximately 600 million years ago, but their proliferation at that time is poorly understood. Recent marine phosphorites spatially correlate with the habitats of vacuolated sulfide-oxidizing bacteria that store polyphosphates under oxic conditions to be utilized under sulfidic conditions. Hydrolysis of the stored polyphosphate results in the rapid precipitation of the phosphate-rich mineral apatite-providing a mechanism to explain the association between modern phosphorites and these bacteria. Whether sulfur bacteria were important to the formation of ancient phosphorites has been unresolved. Here, we present the remains of modern sulfide-oxidizing bacteria that are partially encrusted in apatite, providing evidence that bacterially mediated phosphogenesis can rapidly permineralize sulfide-oxidizing bacteria and perhaps other types of organic remains. We also describe filamentous microfossils that resemble modern sulfide-oxidizing bacteria from two major phosphogenic episodes in the geologic record. These microfossils contain sulfur-rich inclusions that may represent relict sulfur globules, a diagnostic feature of modern sulfide-oxidizing bacteria. These findings suggest that sulfur bacteria, which are known to mediate the precipitation of apatite in modern sediments, were also present in certain phosphogenic settings for at least the last 600 million years. If polyphosphate-utilizing sulfide-oxidizing bacteria also played a role in the formation of ancient phosphorites, their requirements for oxygen, or oxygen-requiring metabolites such as nitrate, might explain the temporal correlation between the first appearance of globally distributed marine phosphorites and increasing oxygenation of Neoproterozoic oceans.