Background: Phylogeographic composition of M. tuberculosis populations reveals associations between lineages and human populations that might have implications for the development of strategies to control the disease. In Latin America, lineage 4 or the Euro-American, is predominant with considerable variations among and within countries. In Colombia, although few studies from specific localities have revealed differences in M. tuberculosis populations, there are still areas of the country where this information is lacking, as is a comparison of Colombian isolates with those from the rest of the world. Principal Findings: A total of 414 M. tuberculosis isolates from adult pulmonary tuberculosis cases from three Colombian states were studied. Isolates were genotyped using IS6110-restriction fragment length polymorphism (RFLP), spoligotyping, and 24-locus Mycobacterial interspersed repetitive units variable number tandem repeats (MIRU-VNTRs). SIT42 (LAM9) and SIT62 (H1) represented 53.3% of isolates, followed by 8.21% SIT50 (H3), 5.07% SIT53 (T1), and 3.14% SIT727 (H1). Composite spoligotyping and 24-locus MIRU- VNTR minimum spanning tree analysis suggest a recent expansion of SIT42 and SIT62 evolved originally from SIT53 (T1). The proportion of Haarlem sublineage (44.3%) was significantly higher than that in neighboring countries. Associations were found between M. tuberculosis MDR and SIT45 (H1), as well as HIV-positive serology with SIT727 (H1) and SIT53 (T1). Conclusions: This study showed the population structure of M. tuberculosis in several regions from Colombia with a dominance of the LAM and Haarlem sublineages, particularly in two major urban settings (Medellín and Cali). Dominant spoligotypes were LAM9 (SIT 42) and Haarlem (SIT62). The proportion of the Haarlem sublineage was higher in Colombia compared to that in neighboring countries, suggesting particular conditions of co-evolution with the corresponding human population that favor the success of this sublineage.