Mycobacterium lepraemurium is the causative agent of murine leprosy, a chronic, granulomatous disease similar to human leprosy. Due to the similar clinical manifestations of human and murine leprosy and the difficulty of growing both bacilli axenically, Mycobacterium leprae and M. lepraemurium were once thought to be closely related, although it was later suggested that M. lepraemurium might be related to Mycobacterium avium. In this study, the complete genome of M. lepraemurium was sequenced using a combination of PacBio and Illumina sequencing. Phylogenomic analyses confirmed that M. lepraemurium is a distinct species within the M. avium complex (MAC). The M. lepraemurium genome is 4.05 Mb in length, which is considerably smaller than other MAC genomes, and it comprises 2,682 functional genes and 1,139 pseudogenes, which indicates that M. lepraemurium has undergone genome reduction. An error-prone repair homologue of the DNA polymerase III alpha-subunit was found to be nonfunctional in M. lepraemurium, which might contribute to pseudogene formation due to the accumulation of mutations in nonessential genes. M. lepraemurium has retained the functionality of several genes thought to influence virulence among members of the MAC. IMPORTANCE Mycobacterium lepraemurium seems to be evolving toward a minimal set of genes required for an obligatory intracellular lifestyle within its host, a niche seldom adopted by most mycobacteria, as they are free-living. M. lepraemurium could be used as a model to elucidate functions of genes shared with other members of the MAC. Its reduced gene set can be exploited for studying the essentiality of genes in related pathogenic species, which might lead to discovery of common virulence factors or clarify host-pathogen interactions. M. lepraemurium can be cultivated in vitro only under specific conditions and even then with difficulty. Elucidating the metabolic (in) capabilities of M. lepraemurium will help develop suitable axenic media and facilitate genetic studies.