The present article reports the textures, whole-rock and mineral chemistry, and mineral reactions under greenschist- to amphibolite-facies conditions of Proterozoic aluminum phosphate–bearing metaquartzites from central Madagascar and from the Espinhaço fold belt in Brazil. Based on this information, the mechanism of aluminum phosphate genesis in the protolith of the metaquartzites and the behavior of phosphates (lazulite, augelite, trolleite, svanbergite, goyazite-crandallite, berlinite, and xenotime) during low-grade amphibolite-facies metamorphism is discussed. In Precambrian marine sandstones, aluminum phosphate was a potentially important phosphorus sink before the beginning of abundant organic and large-scale calcium phosphate deposition in the Neoproterozoic. A compilation of alternative calcium phosphate (apatite) deposits in the Precambrian confirms their insignificance for phosphorus fixation before the Neoproterozoic. Efficient phosphorus burial in aluminum phosphates inhibited the rapid buildup of phosphorus nutrient levels in the early Precambrian oceans.