The contribution of horizontal gene transfer (HGT) to the evolution of Mycobacterium tuberculosis -- the main causal agent of tuberculosis in humans -- and closely related members of the M. tuberculosis complex remains poorly understood. Using a combination of genome-wide parametric analyses, we have identified 48 M. tuberculosis chromosomal regions with atypical characteristics, potentially due to HGT. These specific regions account for 4.5% of the genome (199 kb) and include 256 genes. Many display features typical of the genomic islands found in other bacteria, including residual material from mobile genetic elements, flanking direct repeats, insertion in the vicinity of tRNA sequences, and genes with putative or documented virulence functions. Southern blotting analysis of nine of these 48 regions confirmed their presence in "Mycobacterium prototuberculosis," the ancestral species of the M. tuberculosis complex. Finally, our results strongly suggest that the ancestor of the tubercle bacilli was an environmental bacillus that exchanged genetic material with other bacterial species, including Proteobacteria in particular, present in its surroundings. This study describes a rational approach to searching for mycobacterial virulence genes, and highlights the importance of dissecting gene transfer networks to improve our understanding of mycobacterial pathogenicity and evolution.