Multiple genome-wide association analyses have investigated susceptibility to bovine paratuberculosis, but few loci have been identified across independent cattle populations. A SNP-based gene set enrichment analysis (GSEA-SNP) allows expanded identification of genes with moderate effects on a trait through the enrichment of gene sets instead of identifying only few loci with large effects. Therefore, the objective of this study was to identify genes that were moderately associated with Mycobacterium avium ssp. paratuberculosis (Map) tissue infection using GSEA-SNP in Holstein cattle from the Pacific Northwest (PNW; n = 205) and from the PNW and Northeast (PNW+NE; n = 245) which were previously genotyped with the Illumina BovineSNP50 BeadChip. The GSEA-SNP utilized 4389 gene sets from five databases. For each annotated gene in the UMD3.1 assembly (n = 19,723), the most significant SNP within each gene and its surrounding region (10 kb up- and downstream) was selected as a proxy for that gene. Any gene set with a normalized enrichment score > 2.5 was considered enriched. Thirteen gene sets (8 PNW GSEA-SNP; 5 PNW+NE) were enriched in these analyses and all have functions that relate to nuclear factor kappa beta. Nuclear factor kappa beta is critical to gut immune responses, implicated in host immune responses to other mycobacterial diseases, and has established roles in inflammation as well as cancer. Gene sets and genes moderately associated with Map infection could be used in genomic selection to allow producers to select for less susceptible cattle, lower the prevalence of the disease, and reduce economic losses.