Trichodesmium is a biogeochemically important marine cyanobacterium, responsible for a significant proportion of the annual 'new' nitrogen introduced into the global ocean. These non-heterocystous filamentous diazotrophs employ a potentially unique strategy of near-concurrent nitrogen fixation and oxygenic photosynthesis, potentially burdening Trichodesmium with a particularly high iron requirement due to the iron-binding proteins involved in these processes. Iron availability may therefore have a significant influence on the biogeography of Trichodesmium. Previous investigations of molecular responses to iron stress in this keystone marine microbe have largely been targeted. Here a holistic approach was taken using a label-free quantitative proteomics technique (MSE) to reveal a sophisticated multi-faceted proteomic response of Trichodesmium erythraeum IMS101 to iron stress. Increased abundances of proteins known to be involved in acclimation to iron stress and proteins known or predicted to be involved in iron uptake were observed, alongside decreases in the abundances of iron-binding proteins involved in photosynthesis and nitrogen fixation. Preferential loss of proteins with a high iron content contributed to overall reductions of 55-60% in estimated proteomic iron requirements. Changes in the abundances of iron-binding proteins also suggested the potential importance of alternate photosynthetic pathways as Trichodesmium reallocates the limiting resource under iron stress. Trichodesmium therefore displays a significant and integrated proteomic response to iron availability that likely contributes to the ecological success of this species in the ocean.