Saharan dust is an important phosphorus (P) supply to remote and oligotrophic parts of the oceans and American lowland tropical rainforests. Phosphorus speciation in aeolian dust ultimately controls the release and bioavailability of P after dust deposition, but the speciation in Saharan dust and its change during the trans-Atlantic transport remains unclear. Using P K-edge X-ray absorption near edge structure (XANES) spectroscopy, we showed that with increasing dust traveling distance from the Sahara Desert to Cape Verde and to Puerto Rico, about 570 and 4000 km, respectively, the proportion of Ca-bound P (Ca-P), including both apatite and non-apatite forms, decreased from 68–73% to 50–71% and to 21–37%. The changes were accompanied by increased iron/aluminum-bound P proportion from 14–25% to 23–46% and to 44–73%, correspondingly. Laboratory simulation experiments suggest that the changes in P speciation can be ascribed to increasing degrees of particle sorting and atmospheric acidification during dust transport. The presence of relatively soluble non-apatite Ca-P in the Cape Verde dust but not in the Puerto Rico dust is consistent with the higher P water solubility of the former than the latter. Our findings provide insights into the controls of atmospheric processes on P speciation, solubility, and stability in Saharan dust.