Mycobacterium bovis BCG has the potential to be an effective live vector for multivalent vaccines. However, most mycobacterial cloning vectors rely on antibiotic resistance genes as selectable markers, which would be undesirable in any practical vaccine. Here we report the use of auxotrophic complementation as a selectable marker that would be suitable for use in a recombinant vaccine. A BCG auxotrophic for the amino acid leucine was constructed by knocking out the leuD gene by unmarked homologous recombination. Expression of leuD on a plasmid not only allowed complementation, but also acted as a selectable marker. Removal of the kanamycin resistance gene, which remained necessary for plasmid manipulations in Escherichia coli, was accomplished by two different methods: restriction enzyme digestion followed by re-ligation before BCG transformation, or by Cre–loxP in vitro recombination mediated by the bacteriophage P1 Cre Recombinase. Stability of the plasmid was evaluated during in vitro and in vivo growth of the recombinant BCG in comparison to selection by antibiotic resistance. The new system was highly stable even during in vivo growth, as the selective pressure is maintained, whereas the conventional vector was unstable in the absence of selective pressure. This new system will now allow the construction of potential recombinante vaccine strains using stable multicopy plasmid vectors without the inclusion of antibiotic resistance markers.