Comparisons of evolutionary divergent promoter sequences have revealed that gross rearrangements of pre-existing blocks into new combinations play a central role during the evolution of regulatory regions. The noncoding region upstream of the leukotoxin operon was analyzed in six Mannheimia strains (Mhae1, Mhae2, Mglu, Mrum, Mgra, Mvar). The region from +30 to -208 showed sequence conservation in the Mannheimia strains, suggesting that this region represents an ancestral promoter block that has been maintained vertically in genus Mannheimia. Analyses of the 5¢ flanking regions showed the existence of three blocks that are restricted to specific lineages, of which the ancestral block is conserved in Mrum and Mvar. The transcriptional unit artJ has been shuffled into the upstream region in the last common ancestor of Mha1, Mha2 and Mglu. The corresponding non-coding DNA region ranging from -209 to -376 contains at least one positive regulatory element, suggesting early divergence within the promoter family and the emergence of a lineage with increased promoter strength. Tandem duplication of the pattern ACAAAAAACA has occurred in the ancestral Mhae1 promoter after the Mhae1 and Mhae2 ancestors diverged. The build-in A₆-tract is inserted in phase with three ancestral tandem repeats containing one A₆-tract each, which might have increased gene expression from the Mhae1 promoter. Phylogenetic analyses of the promoter and 16S rRNA sequences showed that the Mgra branch in the promoter tree was significantly longer than the corresponding branch in the 16S rRNA tree (p = 0.004). These data reflect a high rate of nucleotide substitution in the ancestral Mgra promoter and can be interpreted as pseudogenization. Thus, the mosaic structure of the leukotoxin promoter region has continually been shuffled into new combinations through rearrangements of pre-existing blocks. We suggest that some of these changes could have served to alter either the level of gene expression or the responsiveness of the promoter to trans stimuli.