Polybrominated diphenyl ethers (PBDEs) are persistent and bioaccumulative anthropogenic and natural chemicals that are broadly distributed in the marine environment. PBDEs are potentially toxic due to inhibition of various mammalian signaling pathways and enzymatic reactions. PBDE isoforms vary in toxicity in accordance with structural differences, primarily in the number and pattern of hydroxyl moieties afforded upon a conserved core structure. Over four decades of isolation and discovery-based efforts have established an impressive repertoire of natural PBDEs. Based on our recent reports describing the bacterial biosyntheses of PBDEs, we predicted the presence of additional classes of PBDEs to those previously identified from marine sources. Using mass spectrometry and NMR spectroscopy, we now establish the existence of new structural classes of PBDEs in marine sponges. Our findings expand the chemical space explored by naturally produced PBDEs, which may inform future environmental toxicology studies. Furthermore, we provide evidence for iodinated PBDEs and direct attention toward the contribution of promiscuous halogenating enzymes in further expanding the diversity of these polyhalogenated marine natural products.