Mismatch repair (MMR) is a near ubiquitous pathway, essential for the maintenance of genome stability. Members of the MutS and MutL protein families perform key steps in mismatch correction. Despite the major importance of this repair pathway, MutS-MutL are absent in almost all Actinobacteria and many Archaea. However, these organisms exhibit rates and spectra of spontaneous mutations similar to MMR-bearing species, suggesting the existence of an alternative to the canonical MutS-MutL-based MMR. Here we report that Mycobacterium smegmatis NucS/EndoMS, a putative endonuclease with no structural homology to known MMR factors, is required for mutation avoidance and anti-recombination, hallmarks of the canonical MMR. Furthermore, phenotypic analysis of naturally occurring polymorphic NucS in a M. smegmatis surrogate model, suggests the existence of M. tuberculosis mutator strains. The phylogenetic analysis of NucS indicates a complex evolutionary process leading to a disperse distribution pattern in prokaryotes. Together, these findings indicate that distinct pathways for MMR have evolved at least twice in nature.