The β-barrel assembly machine (BAM) complex is an essential feature of all bacteria with an outer membrane. The core subunit of the BAM complex is BamA and, in Escherichia coli, four lipoprotein subunits: BamB, BamC, BamD and BamE, also function in the BAM complex. Hidden Markov model analysis was used to comprehensively assess the distribution of subunits of the BAM lipoproteins across all subclasses of proteobacteria. A patchwork distribution was detected which is readily reconciled with the evolution of the α-, β-, γ-, δ- and ε-proteobacteria. Our findings lead to a proposal that the ancestral BAM complex was composed of two subunits: BamA and BamD, and that BamB, BamC and BamE evolved later in a distinct sequence of events. Furthermore, in some lineages novel lipoproteins have evolved instead of the lipoproteins found in E. coli. As an example of this concept, we show that no known species of α-proteobacteria has a homologue of BamC. However, purification of the BAM complex from the model α-proteobacterium Caulobacter crescentus identified a novel subunit we refer to as BamF, which has a conserved sequence motif related to sequences found in BamC. BamF and BamD can be eluted from the BAM complex under similar conditions, mirroring the BamC:D module seen in the BAM complex of γ-proteobacteria such as E. coli.