Johne's disease, or paratuberculosis, is a chronic granulomatous enteritis in ruminants caused by Mycobacterium avium subsp. paratuberculosis (MAP) affecting principally cattle, sheep and goats. Primarily, there are two clinical signs: cachexia and chronic diarrhea (less common in goats and sheep). This disease results in considerable economic losses in livestock industry, particularly the dairy sector. The route of transmission is mostly by the fecal-oral route, but hygienic measures and culling of shedding animals are not sufficient to eradicate this disease. Moreover, diagnostic tools available at this moment are not powerful enough to perform early and specific diagnosis. Existing vaccines, based on whole killed or live-attenuated bacteria, can delay the onset of clinical symptoms but do not protect against infection. Moreover, vaccinated animals develop antibodies that interfere with existing serodiagnostic tests for paratuberculosis and they become reactive in the tuberculin skin test, used for the control of bovine tuberculosis. This review summarizes the current knowledge of the immune responses induced by MAP infection, with focus on cattle studies. It provides an overview of the existing MAP vaccines and comments on the development of second-generation subunit vaccines based on new technologies.