The factors that control the growth and nitrogen fixation rates of marine diazotrophs such as Trichodesmium have been intensively studied because of the role that these processes have in the global cycling of carbon and nitrogen, and in the sequestration of carbon to the deep sea. Because the phosphate concentrations of many ocean gyres are low, the bioavailability of the larger, chemically heterogeneous pool of dissolved organic phosphorus could markedly influence Trichodesmium physiology. Here we describe the induction, by phosphorus stress, of genes from the Trichodesmium erythraeum IMS101 genome that are predicted to encode proteins associated with the high-affinity transport and hydrolysis of phosphonate compounds by a carbon-phosphorus lyase pathway. We show the importance of these genes through expression analyses with T. erythraeum from the Sargasso Sea. Phosphonates are known to be present in oligotrophic marine systems, but have not previously been considered to be bioavailable to marine diazotrophs. The apparent absence of genes encoding a carbon-phosphorus lyase pathway in the other marine cyanobacterial genomes suggests that, relative to other phytoplankton, Trichodesmium is uniquely adapted for scavenging phosphorus from organic sources. This adaptation may help to explain the prevalence of Trichodesmium in low phosphate, oligotrophic systems.