Phosphorus is an essential nutrient for life. In the ocean, phosphorus burial regulates marine primary production(1,2). Phosphorus is removed from the ocean by sedimentation of organic matter, and the subsequent conversion of organic phosphorus to phosphate minerals such as apatite, and ultimately phosphorite deposits(3,4). Bacteria are thought to mediate these processes(5), but the mechanism of sequestration has remained unclear. Here, we present results from laboratory incubations in which we labelled organic-rich sediments from the Benguela upwelling system, Namibia, with a P-33-radiotracer, and tracked the fate of the phosphorus. We show that under both anoxic and oxic conditions, large sulphide-oxidizing bacteria accumulate P-33 in their cells, and catalyse the nearly instantaneous conversion of phosphate to apatite. Apatite formation was greatest under anoxic conditions. Nutrient analyses of Namibian upwelling waters and sediments suggest that the rate of phosphate-to-apatite conversion beneath anoxic bottom waters exceeds the rate of phosphorus release during organic matter mineralization in the upper sediment layers. We suggest that bacterial apatite formation is a significant phosphorus sink under anoxic bottom-water conditions. Expanding oxygen minimum zones are projected in simulations of future climate change(6), potentially increasing sequestration of marine phosphate, and restricting marine productivity.