Recombinant mycobacterial vaccine vehicles capable of expressing DNA of interest which encodes at least one protein antigen for at least one pathogen against which an immune response is desired and which can be incorporated into the mycobacteria or stably integrated into the mycobacterial genome. The vaccine vehicles are useful for administration to mammalian hosts for purposes of immunization. A recombinant vector which replicates in E. coli but not in mycobacteria is also disclosed. The recombinant vector includes 1) a mycobacterial gene or portions thereof, necessary for recombination with homologous sequences in the genome of mycobacteria transformed with the recombinant plasmid; 2) all or a portion of a gene which encodes a polypeptide or protein whose expression is desired in mycobacteria transformed with the recombinant plasmid; 3) DNA sequences necessary for replication and selection in E. coli; and 4) DNA sequences necessary for selection in mycobacteria (e.g., drug resistance). The present invention also relates to two types of recombinant vectors useful in introducing DNA of interest into mycobacteria, where it is expressed. One type of vector is a recombinant phasmid capable of replicating as a plasmid in E. coli and of lysogenizing a mycobacterial host. The other type of vector is a recombinant plasmid which can be introduced into mycobacteria, where it is stably maintained extrachromosomally.