Compositions of immunogenic proteins of Mycobacterium avium subspecies paratuberculosis (MAP) are effective for stimulating a protective immune response in animals against MAP. Combinations of MAP1087 with two or more of MAP1204, MAP1272c and MAP2077c are effective for stimulating a protective immune response in animals against MAP and can be administered as vaccines against paratuberculosis (Johne's disease). Induction of the immune response significantly reduces or eliminates colonization of the animal by MAP, and consequently reduces or eliminates the symptoms of clinical disease in animals infected with MAP and reduces or eliminates fecal shedding of MAP. Vaccination with the compositions provides protection against clinical disease and reduces transmission of MAP infection within a herd.