We describe a multilocus short sequence repeat (MLSSR) sequencing approach for the genotyping of Mycobacterium avium subsp. paratuberculosis (M. paratuberculosis) strains. Preliminary analysis identified 185 mono-, di-, and trinucleotide repeat sequences dispersed throughout the M. paratuberculosis genome, of which 78 were perfect repeats. Comparative nucleotide sequencing of the 78 loci of six M. paratuberculosis isolates from different host species and geographic locations identified a subset of 11 polymorphic short sequence repeats (SSRs), with an average of 3.2 alleles per locus. Comparative sequencing of these 11 loci was used to genotype a collection of 33 M. paratuberculosis isolates representing different multiplex PCR for IS900 loci (MPIL) or amplified fragment length polymorphism (AFLP) types. The analysis differentiated the 33 M. paratuberculosis isolates into 20 distinct MLSSR types, consistent with geographic and epidemiologic correlates and with an index of discrimination of 0.96. MLSSR analysis was also clearly able to distinguish between sheep and cattle isolates of M. paratuberculosis and easily and reproducibly differentiated strains representing the predominant MPIL genotype (genotype A18) and AFLP genotypes (genotypes Z1 and Z2) of M. paratuberculosis described previously. Taken together, the results of our studies suggest that MLSSR sequencing enables facile and reproducible high-resolution subtyping of M. paratuberculosis isolates for molecular epidemiologic and population genetic analyses.