Background: Human tuberculosis (TB) is caused by seven phylogenetic lineages of the Mycobacterium tuberculosis complex (MTBC), Lineage 1–7. Recent advances in rapid genotyping of MTBC based on single nucleotide polymorphisms (SNP), allow for rapid and phylogenetically robust strain classification, paving the way for defining genotype-phenotype relationships in clinical settings. Such studies have revealed that, in addition to host and environmental factors, different strains of the MTBC influence the outcome of TB infection and disease. In Tanzania, such molecular epidemiological studies of TB however are scarce in spite of a high TB burden. Methods and Findings: Here we used a SNP-typing method to genotype a nationwide collection of 2,039 MTBC clinical isolates obtained from new and retreatment TB cases diagnosed in 2012 and 2013. Four lineages, namely Lineage 1–4 were identified. The distribution and frequency of these lineages varied across the regions but overall, Lineage 4 was the most frequent (n = 866, 42.5%), followed by Lineage 3 (n = 681, 33.4%) and 1 (n = 336, 16.5%), with Lineage 2 being the least frequent (n = 92, 4.5%). A total of 64 (3.1%) isolates could not be assigned to any lineage. We found Lineage 2 to be associated with female sex (adjusted odds ratio [aOR] 2.25; 95% confidence interval [95% CI] 1.38 – 3.70, p < 0.001) and retreatment (aOR 1.78; 95% CI 1.00 – 3.02, p = 0.040). We found no associations between MTBC lineage and patient age or HIV status. Our sublineage typing based on spacer oligotyping revealed the presence of mainly EAI, CAS and LAM families. Finally, we detected low levels of multidrug resistant isolates among a subset of retreatment cases Conclusions: This study provides novel insights into the influence of pathogen–related factors on the TB epidemic in Tanzania.