Genetic dissection of M. tuberculosis is complicated by its slow growth and its high rate of illegitimate recombination relative to homologous DNA exchange. We report here the development of a facile allelic exchange system by identification and expression of mycobacteriophage-encoded recombination proteins, adapting a strategy developed previously for recombineering in Escherichia coli. Identifiable recombination proteins are rare in mycobacteriophages, and only 1 of 30 genomically characterized mycobacteriophages (Che9c) encodes homologs of both RecE and RecT. Expression and biochemical characterization show that Che9c gp60 and gp61 encode exonuclease and DNA-binding activities, respectively, and expression of these proteins substantially elevates recombination facilitating allelic exchange in both M. smegmatis and M. tuberculosis. Mycobacterial recombineering thus provides a simple approach for the construction of gene replacement mutants in both slow- and fast-growing mycobacteria.