BACKGROUND: Mycobacterium ulcerans is an unusual bacterial pathogen with elusive origins. While closely related to the aquatic dwelling M. marinum, M. ulcerans has evolved the ability to produce the immunosuppressive polyketide toxin mycolactone and cause the neglected tropical disease Buruli ulcer. Other mycolactone-producing mycobacteria (MPM) have been identified in fish and frogs and given distinct species designations (M. pseudoshottsii, M. shinshuense, M. liflandii and M. marinum), however the evolution of M. ulcerans and its relationship to other MPM has not been defined. Here we report the comparative analysis of whole genome sequences from 30 MPM and five M. marinum. RESULTS: A high-resolution phylogeny based on genome-wide single nucleotide polymorphisms (SNPs) showed that M. ulcerans and all other MPM represent a single clonal group that evolved from a common M. marinum progenitor. The emergence of the MPM was driven by the acquisition of the pMUM plasmid encoding genes for the biosynthesis of mycolactones. This change was accompanied by the loss of at least 185 genes, with a significant overrepresentation of genes associated with cell wall functions. Cell wall associated genes also showed evidence of substantial adaptive selection, suggesting cell wall remodeling has been critical for the survival of MPM. Fine-grain analysis of the MPM complex revealed at least three distinct lineages, one of which comprised a highly clonal group, responsible for Buruli ulcer in Africa and Australia. This indicates relatively recent transfer of M. ulcerans between these continents, which represent the vast majority of the global Buruli ulcer burden. Our data provide SNPs and gene sequences that can differentiate M. ulcerans lineages, suitable for use in the diagnosis and surveillance of Buruli ulcer. CONCLUSIONS: M. ulcerans and all mycolactone-producing mycobacteria are specialized variants of a common Mycobacterium marinum progenitor that have adapted to live in restricted environments. Examination of genes lost or retained and now under selective pressure suggests these environments might be aerobic, and extracellular, where slow growth, production of an immune suppressor, cell wall remodeling, loss or modification of cell wall antigens, and biofilm-forming ability provide a survival advantage. These insights will guide our efforts to find the elusive reservoir(s) of M. ulcerans and to understand transmission of Buruli ulcer.