Background: Bovine paratuberculosis, or Johne's disease (JD), is a contagious and incurable disease caused by Mycobacterium avium subsp. paratuberculosis (MAP). It has adverse effects on animal welfare and is very difficult to control, leading to serious economic consequences. An important line of defense to this disease is host genetic resistance to MAP, which, when it will be more fully understood, could be improved through selective breeding. Using a large dataset of Holstein cows (161,253 animals including 56,766 cows with ELISA serological phenotypes and 12,431 animals with genotypes), we applied a single-step single nucleotide polymorphism (SNP) best linear unbiased prediction approach to investigate the genetic determinism underlying resistance to this disease (heritability estimate and identification of relevant genomic regions) and estimated genetic trends, reliability, and relative risk factors associated with genomic predictions. Results: Resistance to JD was moderately heritable (0.14) and 16 genomic regions were detected that accounted for at least 0.05% of the breeding values variance (GV) in resistance to JD, and were located on chromosomes 1, 3, 5, 6, 7, 19, 20, 21, 23, 25, and 27, with the highest percentage of variance explained by regions on chromosomes 23 (0.36% GV), 5 (0.22% GV), 1 (0.14% GV), and 3 (0.13% GV). When estimated for the whole chromosomes, the autosomes with the largest overall contributions were chromosomes 3 (5.3% GV), 10 (4.8%), 23 (4.7%), 1 (3.6%), 7 (3.4%), 5 (2.9%), 12 (2.5%), 11 (2.2%), and 13 (2%). We estimated a slightly favorable genetic trend in resistance to JD over the last two decades, which can be explained by a low positive genetic correlation between resistance to JD and total merit index (+ 0.06). Finally, in a validation population of 907 cows, relatively reliable genomic predictions (reliability = 0.55) were obtained, which allowed the identification of cows at high risk of infection. Conclusions: This study provides new insights into the genetic determinism of resistance to JD and shows that this trait can be predicted from SNP genotypes. It has led to the implementation of a single-step genomic evaluation that should rapidly become an effective tool for controlling paratuberculosis on French Holstein farms.