Bovine paratuberculosis is a disease caused by Mycobacterium avium ssp. paratuberculosis (MAP). Most infected cows are culled before they reach clinical stage, leading to the premature slaughter of many animals and significant economic losses. Several genetic variants have been reported associated with host susceptibility to MAP. The objective of this study was to validate a whole genome genotyping-by-sequencing (GBS) method to identify single nucleotide polymorphisms (SNPs) associated with bovine paratuberculosis. Animals were selected from 10 farms in the province of Quebec. Fecal and blood samples were collected to identify 24 MAP infectious status by fecal culture and serum ELISA and 24 healthy cows. Two GBS methods were compared: a conventional (restriction enzymes PstI and MspI at 5′/3′ used to construct DNA libraries) method (CM) and CM with more selective primers to reduce the complexity of the libraries (RM). DNA was extracted from isolated peripheral blood monocyte cells. Multiplexed libraries (48 libraries per lane) were subjected to 100-bp single-end sequencing on an Illumina HiSeq 2000 system. Reads that passed all filtering criteria were mapped to the bovine genome (Bta_4.6.1). The SNPs were called using the Universal Network-Enabled Analysis Kit and 30,266 and 82,593 passed the quality control steps for the CM and the RM methods, respectively. Using the SVS GoldenHelix software, 3,653 (CM) and 17,413 (RM) SNPs were associated with regions that are not intergenic. Associated genes are linked to biological processes related to the immune system and to responses to stimuli, such as defense responses to bacteria. Analysis confirmed that 8 (CM) and 19 (RM) SNPs were associated with MAP infectious status (P < 0.05). Validation of their genetic association with bovine paratuberculosis are currently performed by SEQUENOM mass spectrometry using a larger group of animals (n = 800). The reduction of the complexity of the genome produced a larger number of qualified genotypes compared with the conventional method suggesting that this GBS strategy provides a greater reading depth, which increases the quality of each genotype.