The nitrogen (N)-fixing cyanobacterium Trichodesmium is globally distributed in warm, oligotrophic oceans, where it contributes a substantial proportion of new N and fuels primary production. These photoautotrophs form macroscopic colonies that serve as relatively nutrient-rich substrates that are colonized by many other organisms. The nature of these associations may modulate ocean N and carbon (C) cycling, and can offer insights into marine co-evolutionary mechanisms. Here we integrate multiple omics-based and experimental approaches to investigate Trichodesmium-associated bacterial consortia in both laboratory cultures and natural environmental samples. These efforts have identified the conserved presence of a species of Gammaproteobacteria (Alteromonas macleodii), and enabled the assembly of a near-complete, representative genome. Interorganismal comparative genomics between A. macleodii and Trichodesmium reveal potential interactions that may contribute to the maintenance of this association involving iron and phosphorus acquisition, vitamin B12 exchange, small C compound catabolism, and detoxification of reactive oxygen species. These results identify what may be a keystone organism within Trichodesmium consortia and support the idea that functional selection has a major role in structuring associated microbial communities. These interactions, along with likely many others, may facilitate Trichodesmium's unique open-ocean lifestyle, and could have broad implications for oligotrophic ecosystems and elemental cycling.