Reliable molecular detection of Mycobacterium ulcerans in environmental samples is essential to study the ecology and transmission of this important human pathogen. Variable number tandem repeat (VNTR) typing is a valuable method for distinguishing M. ulcerans isolates from different geographic regions and for distinguishing M. ulcerans from other members of the Mycobacterium marinum/M. ulcerans complex, but its application to environmental samples has not yet been evaluated systematically. This study compares the sensitivity and specificity of PCR detection of 13 VNTR loci to determine the best loci for the analysis of environmental samples. This study demonstrates that VNTR typing using selected loci can be a useful addition to established molecular methods for detecting M. ulcerans in the environment and highlights some of the issues encountered when using molecular methods to detect microorganisms in environmental samples. When applied to environmental samples collected from an endemic region in Victoria, Australia, VNTR typing confirmed that the strain of M. ulcerans being detected was indistinguishable from the strain causing disease in humans in that region.