Johne's disease or paratuberculosis is a chronic debilitating disease in ruminants caused by Mycobacterium avium subsp. paratuberculosis (MAP). The disease causes significant economic losses in livestock industries worldwide. There are no effective control measures to eradicate the disease because there are no appropriate diagnostic methods to detect subclinically infected animals. Therefore, it is very difficult to control the disease using only test and cull strategies. Vaccination against paratuberculosis has been considered as an alternative strategy to control the disease when combined with management interventions. Understanding host-pathogen interactions is extremely important to development of vaccines. It has long been known that Th1-mediated cellular immune responses are play a crucial role in protection against MAP infection. However, recent studies suggested that innate immune responses are more closely related to protective effects than adaptive immunity. Based on this understanding, several attempts have been made to develop vaccines against paratuberculosis. A variety of ideas for designing novel vaccines have emerged, and the tests of the efficacy of these vaccines are conducted constantly. However, no effective vaccines are commercially available. In this study, studies of the development of vaccines for MAP were reviewed and summarized.