The production of pentabromopseudilin and related brominated compounds by Pseudoalteromonas spp. has recently been linked to the bmp biosynthetic gene cluster. This study explored the distribution and evolutionary history of this gene cluster in the genus Pseudoalteromonas. A phylogeny of the genus revealed numerous clades that do not contain type strains, suggesting considerable species level diversity has yet to be described. Comparative genomics revealed four distinct versions of the gene cluster distributed among 19 of the 101 Pseudoalteromonas genomes examined. These were largely localized to the least inclusive clades containing the Pseudoalteromonas luteoviolacea and Pseudoalteromonas phenolica type strains and show clear evidence of gene and gene cluster loss in certain lineages. Bmp gene phylogeny is largely congruent with the Pseudoalteromonas species phylogeny, suggesting vertical inheritance within the genus. However, the gene cluster is found in three different genomic environments suggesting either chromosomal rearrangement or multiple acquisition events. Bmp conservation within certain lineages suggests the encoded products are highly relevant to the ecology of these bacteria.