The efflux pumps from the Resistance-Nodulation-Division family, RND, are main contributors to intrinsic antibiotic resistance in Gram-negative bacteria. Among this family, the MdtABC pump is unusual by having two inner membrane components. The two components, MdtB and MdtC are homologs, therefore it is evident that the two components arose by gene duplication. In this paper, we describe the results obtained from a phylogenetic analysis of the MdtBC pumps in the context of other RNDs. We show that the individual inner membrane components (MdtB and MdtC) are conserved throughout the Proteobacterial species and that their existence is a result of a single gene duplication. We argue that this gene duplication was an ancient event which occurred before the split of Proteobacteria into Alpha-, Beta- and Gamma- classes. Moreover, we find that the MdtABC pumps and the MexMN pump from Pseudomonas aeruginosa share a close common ancestor, suggesting the MexMN pump arose by another gene duplication event of the original Mdt ancestor. Taken together, these results shed light on the evolution of the RND efflux pumps and demonstrate the ancient origin of the Mdt pumps and suggest that the core bacterial efflux pump repertoires have been generally stable throughout the course of evolution.