Paratuberculosis is an infectious disease that is not easily amenable to classical control methods such as treatment and vaccination. Experimental animal models suggest that there could be genetic factors responsible for susceptibility or resistance to infection with the causative agent, Mycobacterium avium subsp. paratuberculosis. The aim of this study was to estimate genetic variation in susceptibility to paratuberculosis in Dutch dairy cattle. Data collected during a vaccination trial, conducted from 1984 to 1994, was used. A total of 3020 cows, with complete pedigree records and infection status at slaughter, were available for analysis. A standard polygenic statistical probit model was used to estimate heritabilities. The estimated heritability of susceptibility to M. avium. subsp. paratuberculosis infection was 0.06 for the overall population. In the subpopulation of vaccinated animals the estimated heritability was 0.09. Other calculations based on the model used in this study argue against a prominent role for vertical transmission. Because the establishment of genetic variation is one of the first steps towards the exploration of the possible use of selection for genetic improvement, the present study provides evidence for the presence of genetic variation in the susceptibility of cattle to paratuberculosis. Because the economic impact of the disease is substantial, the development and application of genetic tools, along with other control methods, could be instrumental in the eradication of paratuberculosis.