Naturally produced polybrominated diphenyl ethers (PBDEs) pervade the marine environment and structurally resemble toxic man-made brominated flame retardants. PBDEs bioaccumulate in marine animals and are likely transferred to the human food chain. However, the biogenic basis for PBDE production in one of their most prolific sources, marine sponges of the order Dysideidae, remains unidentified. Here, we report the discovery of PBDE biosynthetic gene clusters within sponge-microbiome-associated cyanobacterial endosymbionts through the use of an unbiased metagenome-mining approach. Using expression of PBDE biosynthetic genes in heterologous cyanobacterial hosts, we correlate the structural diversity of naturally produced PBDEs to modifications within PBDE biosynthetic gene clusters in multiple sponge holobionts. Our results establish the genetic and molecular foundation for the production of PBDEs in one of the most abundant natural sources of these molecules, further setting the stage for a metagenomic-based inventory of other PBDE sources in the marine environment.