Mycobacterium avium subsp. paratuberculosis is an emerging pathogen of mammals and is being actively investigated as a possible zoonotic agent. The lack of reliable diagnostic assays has hampered rational assessment of the prevalence of this organism in humans and animals. We have used a comparative genomic approach to reveal genomic differences between M. avium subsp. paratuberculosis and its close relative M. avium subsp. avium, a highly prevalent environmental organism. From computational and DNA microarray-based study of two prototype strains, M. avium subsp. avium strain 104 and M. avium subsp. paratuberculosis strain K10, we have uncovered two types of large sequence polymorphisms (LSPs): those present in the former but missing in the latter (LSP(A)s) and those only present in the latter (LSP(P)s). We examined the distribution of 3 LSP(A)s and 17 LSP(P)s across a panel of 383 M. avium complex isolates in order to determine their potential utility for the development of accurate diagnostic tests. Our results show that the absence of LSP(A)8 is 100% specific for the identification of M. avium subsp. paratuberculosis. Of the 17 LSP(P)s, 10 regions were not specific for M. avium subsp. paratuberculosis while 7 were shown to be highly specific (>98%) and, in some cases, highly sensitive as well (up to 95%). These data highlight the need to evaluate these regions across a diverse panel of clinical and environmental isolates and indicate the LSPs best suited for M. avium subsp. paratuberculosis diagnostics.