Bovine paratuberculosis is a highly prevalent chronic infection of the small intestine in cattle, caused by Mycobacterium avium subspecies paratuberculosis. Current control strategies based on test-and-cull and biosecurity measures do not suffice in lowering the prevalence of paratuberculosis in an adequate manner. Therefore, control programmes are in need of an effective vaccine, but at the moment no vaccine is registered for use in cattle in the European Union. This review provides a brief overview of the microbiology, epidemiology and immunology of bovine paratuberculosis, and focuses on recent advances in the development of vaccines against paratuberculosis.