The diazotrophic cyanobacterium, Trichodesmium, is an integral component of the marine nitrogen cycle and contributes significant amounts of new nitrogen to oligotrophic, tropical/subtropical ocean surface waters. Trichodesmium forms macroscopic, fusiform (tufts), spherical (puffs) and raft-like colonies that provide a pseudobenthic habitat for a host of other organisms including marine invertebrates, microeukaryotes and numerous other microbes. The diversity and activity of denitrifying bacteria found in association with the colonies was interrogated using a series of molecular-based methodologies targeting the gene encoding the terminal step in the denitrification pathway, nitrous oxide reductase (nosZ). Trichodesmium spp. sampled from geographically isolated ocean provinces (the Atlantic Ocean, the Red Sea and the Indian Ocean) were shown to harbor highly similar, taxonomically related communities of denitrifiers whose members are affiliated with the Roseobacter clade within the Rhodobacteraceae (Alphaproteobacteria). These organisms were actively expressing nosZ in samples taken from the mid-Atlantic Ocean and Red Sea implying that Trichodesmium colonies are potential sites of nitrous oxide consumption and perhaps earlier steps in the denitrification pathway also. It is proposed that coupled nitrification of newly fixed N is the most likely source of nitrogen oxides supporting nitrous oxide cycling within Trichodesmium colonies.