In a previous report, we described a PCR protocol for the differentiation of the various species of the Mycobacterium tuberculosis complex (MTC) on the basis of genomic deletions (R. C. Huard, L. C. de Oliveira Lazzarini, W. R. Butler, D. van Soolingen, and J. L. Ho, J. Clin. Microbiol. 41:1637-1650, 2003). That report also provided a broad cross-comparison of several previously identified, phylogenetically relevant, long-sequence and single-nucleotide polymorphisms (LSPs and SNPs, respectively). In the present companion report, we expand upon the previous work (i) by continuing the evaluation of known MTC phylogenetic markers in a larger collection of tubercle bacilli (n = 125), (ii) by evaluating additional recently reported MTC species-specific and interspecific polymorphisms, and (iii) by describing the identification and distribution of a number of novel LSPs and SNPs. Notably, new genomic deletions were found in various Mycobacterium tuberculosis strains, new species-specific SNPs were identified for “Mycobacterium canettii,” Mycobacterium microti, and Mycobacterium pinnipedii, and, for the first time, intraspecific single-nucleotide DNA differences were discovered for the dassie bacillus, the oryx bacillus, and the two Mycobacterium africanum subtype I variants. Surprisingly, coincident polymorphisms linked one M. africanum subtype I genotype with the dassie bacillus and M. microti with M. pinnipedii, thereby suggesting closer evolutionary ties within each pair of species than had been previously thought. Overall, the presented data add to the genetic definitions of several MTC organisms as well as fine-tune current models for the evolutionary history of the MTC.