M. avium subsp. paratuberculosis is an emerging pathogen of mammals, and is actively being 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 genomics approach to reveal genomic differences between Mycobacterium 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 avium strain 104 and M. avium paratuberculosis strain K10, we have uncovered 2 types of large sequence polymorphisms (LSPs); those present in the former but missing in the latter (LSP^As), and those only present in the latter (LSP^Ps). We examined the distribution of 3 LSP^As and 17 LSP^Ps across a panel of 383 M. avium complex isolates in order to determine their potential utility for development of accurate diagnostic tests. Our results show that absence of 2 of the LSP^As (LSP^A 8 or LSP^A 14) was 100% specific for the identification of M. avium paratuberculosis. In contrast, only 7 of the 17 LSP^Ps show a comparable degree of specificity. Of these 7, LSP^P2 and LSP^P15 were also highly sensitive for the identification of M. avium paratuberculosis, while the remaining 5 LSP^Ps were only variably present in M. avium paratuberculosis. These data indicate LSPs best suited for diagnosis of M. avium paratuberculosis and highlight the limitations of in silico-driven comparisons of prototype sequences for development of diagnostic assays.