Biological productivity in many ocean regions is controlled by the availability of the nutrient phosphorus. In the Mediterranean Sea, aerosol deposition is a key source of phosphorus and understanding its composition is critical for determining its potential bioavailability. Aerosol phosphorus was investigated in European and North African air masses using phosphorus near-edge X-ray fluorescence spectroscopy (P-NEXFS). These air masses are the main source of aerosol deposition to the Mediterranean Sea. We show that European aerosols are a significant source of soluble phosphorus to the Mediterranean Sea. European aerosols deliver on average 3.5 times more soluble phosphorus than North African aerosols and furthermore are dominated by organic phosphorus compounds. The ultimate source of organic phosphorus does not stem from common primary emission sources. Rather, phosphorus associated with bacteria best explains the presence of organic phosphorus in Mediterranean aerosols. © 2014. American Geophysical Union. All Rights Reserved.