Polybrominated diphenyl ethers (PBDEs) and polybrominated bipyrroles are natural products that bioaccumulate in the marine food chain. PBDEs have attracted widespread attention because of their persistence in the environment and potential toxicity to humans. However, the natural origins of PBDE biosynthesis are not known. Here we report marine bacteria as producers of PBDEs and establish a genetic and molecular foundation for their production that unifies paradigms for the elaboration of bromophenols and bromopyrroles abundant in marine biota. We provide biochemical evidence of marine brominases revealing decarboxylative-halogenation enzymology previously unknown among halogenating enzymes. Biosynthetic motifs discovered in our study were used to mine sequence databases to discover unrealized marine bacterial producers of organobromine compounds.