While bacillus Calmette-Guérin vaccination plays an important role in reducing the morbidity of tuberculosis (TB) infection during childhood, new tuberculosis vaccines are necessary to disrupt the transmission of disease and improve global control of this pathogen. Growing evidence of the presence of meaningful Mycobacterium tuberculosis strain diversity, coupled with the possibility that new vaccines may differentially protect against infection or disease with circulating M. tuberculosis strains, suggest that these vaccines may have complicated effects on disease dynamics. We use a mathematical model to explore the potential effects of strain diversity on the performance of vaccines and find that vaccines offer great promise for improving tuberculosis control, but the expected benefits of mass vaccination will be eroded if strain replacement with M. tuberculosis variants that are not effectively targeted by vaccines occurs. Determining the likelihood of strain replacement will require additional knowledge of the strain specificities of current vaccine candidates, and an improved understanding of the mechanisms of strain interaction, which are responsible for maintaining the diversity of M. tuberculosis within communities.