We compared the genomes of 157 mycobacterial species, representing all major branches of the mycobacterial phylogenetic tree to identify genes and operons enriched among rapid and slow growing mycobacteria. Overlaying growth phenotype on a phylogenetic tree based on 304 core genes suggested that ancestral mycobacteria had a rapid growth phenotype with a single major evolutionary separation into rapid and slow growing sub-genera. We identified 293 genes enriched among rapid growing sub-genera, including genes encoding for amino acid transport/metabolism (e.g., livFGMH operon) and transcription, as well as novel ABC transporters. Loss of the livFGMH and ABC transporter operons among slow growing species suggests that reduced cellular amino acid transport may be growth limiting. Comparative genomic analysis suggests that horizontal gene transfer, from non-mycobacterial genera, may have contributed to niche adaptation and pathogenicity, especially among slow growing species. Interestingly, the mammalian cell entry (mce) operon was found to be ubiquitous, irrespective of growth phenotype or pathogenicity, although protein sequence homology between rapid and slow growing species was low (<50%). This suggests that the mce operon was present in ancestral rapid growing species, but later adapted by slow growing species for use as a mechanism to establish an intra-cellular lifestyle.