Johne's disease, caused by Mycobacterium paratuberculosis infection, is a worldwide problem for the dairy industry and has a possible involvement in Crohn's disease in humans. To identify virulence determinants of this economically important pathogen, a library of 5,060 transposon mutants was constructed using Tn5367 insertion mutagenesis, followed by large-scale sequencing to identify disrupted genes. In this report, 1,150 mutants were analyzed and 970 unique insertion sites were identified. Sequence analysis of the disrupted genes indicated that the insertion of Tn5367 was more prevalent in genomic regions with G+C content (50.5 to 60.5%) lower than the average G+C content (69.3%) of the rest of the genome. Phenotypic screening of the library identified disruptions of genes involved in iron, tryptophan, or mycolic acid metabolic pathways that displayed unique growth characteristics. Bioinformatic analysis of disrupted genes identified a list of potential virulence determinants for further testing with animals. Mouse infection studies showed a significant decrease in tissue colonization by mutants with a disruption in the gcpE, pstA, kdpC, papA2, impA, umaA1, or fabG2_2 gene. Attenuation phenotypes were tissue specific (e.g., for the umaA1 mutant) as well as time specific (e.g., for the impA mutant), suggesting that those genes may be involved in different virulence mechanisms. The identified potential virulence determinants represent novel functional classes that could be necessary for mycobacterial survival during infection and could provide suitable targets for vaccine and drug development against Johne's and Crohn's diseases.