SNP-based gene-set enrichment analysis from single nucleotide polymorphisms, or GSEA-SNP, is a tool to identify candidate genes based on enrichment analysis of sets of genes rather than single SNP associations. The objective of this study was to identify modest-effect genes associated with Mycobacterium avium subsp. paratuberculosis (Map) tissue infection or fecal shedding using GSEA-SNP applied to KEGG pathways or Gene Ontology (GO) gene sets. The Illumina Bovine SNP50 BeadChip was used to genotype 209 Holstein cows for the GSEA-SNP analyses. For each of 13,744 annotated genes genome-wide located within 50 kb of a Bovine SNP50 SNP, the single SNP with the highest Cochran-Armitage Max statistic was used as a proxy statistic for that gene's strength of affiliation with Map. Gene-set enrichment was tested using a weighted Kolmogorov-Smirnov-like running sum statistic with data permutation to adjust for multiple testing. For tissue infection and fecal shedding, no gene sets in KEGG pathways or in GO sets for molecular function or cellular component were enriched for signal. The GO biological process gene set for positive regulation of cell motion (GO:0051272, q = 0.039, 5/11 genes contributing to the core enrichment) was enriched for Map tissue infection, while no GO biological process gene sets were enriched for fecal shedding. GSEA-SNP complements traditional SNP association approaches to identify genes of modest effects as well as genes with larger effects as demonstrated by the identification of one locus that we previously found to be associated with Map tissue infection using a SNP-by-SNP genome-wide association study.