Iron (Fe) bioavailability limits phytoplankton growth in vast ocean regions. Iron-rich dust uplifted from deserts is transported in the atmosphere and deposited on the ocean surface. However, this dust is a poor source of iron for most phytoplankton since dust-bound Fe is poorly soluble in seawater and dust rapidly sinks out of the photic zone. An exception is Trichodesmium, a globally important, N fixing, colony forming, cyanobacterium, which efficiently captures and shuffles dust to its colony core. Trichodesmium and bacteria that reside within its colonies carry out diverse metabolic interactions. Here we show evidence for mutualistic interactions between Trichodesmium and associated bacteria for utilization of iron from dust, where bacteria promote dust dissolution by producing Fe-complexing molecules (siderophores) and Trichodesmium provides dust and optimal physical settings for dissolution and uptake. Our results demonstrate how intricate relationships between producers and consumers can influence productivity in the nutrient starved open ocean.