Although all wild-type bacterial populations exhibit antibiotic tolerance, bacterial mutants with higher or lower tolerant subpopulation sizes have been described. We recently showed that in mycobacteria, phenotypically-resistant subpopulations can grow in bulk-lethal concentrations of rifampicin, a first-line anti-tuberculous antibiotic targeting RNA polymerase. Phenotypic resistance was partly mediated by paradoxical upregulation of RNA polymerase in response to rifampicin. However, naturally occurring mutations that increase tolerance via this mechanism had not been previously described. Here, we used transposon insertional mutagenesis and deep sequencing (Tnseq) to investigate rifampicin-specific phenotypic resistance using two different in vitro models of rifampicin tolerance in Mycobacterium smegmatis. We identify multiple genetic factors that mediate susceptibility to rifampicin. Disruption of one gene, lepA, a translation-associated elongation factor, increased rifampicin tolerance in all experimental conditions. Deletion of lepA increased the subpopulation size that is able to grow in bulk-lethal rifampicin concentrations via upregulation of basal rpoB expression. Moreover, homologous mutations in lepA that are found in clinical Mycobacterium tuberculosis (Mtb) isolates phenocopy lepA deletion to varying degrees. Our study identifies multiple genetic factors associated with rifampicin tolerance in mycobacteria, and may allow correlation of genetic diversity of clinical Mtb isolates with clinically important phenotypes such as treatment regimen duration.