Currently, paratuberculosis vaccines are comprised of crude whole-cell preparations of Mycobacterium avium subsp. paratuberculosis. Although effective in reducing clinical disease and fecal shedding, these vaccines have severe disadvantages as well, including seroconversion of vaccinated animals and granulomatous lesions at the site of vaccination. DNA vaccines can offer an alternative approach that may be safer and elicit more protective responses. In an effort to identify protective M. avium subsp. paratuberculosis sequences, a genomic DNA expression library was generated and subdivided into pools of clones (approximately 1,500 clones/pool). The clone pools were evaluated to determine DNA vaccine efficacy by immunizing mice via gene gun delivery and challenging them with live, virulent M. avium subsp. paratuberculosis. Four clone pools resulted in a significant reduction in the amount of M. avium subsp. paratuberculosis recovered from mouse tissues compared to mice immunized with other clone pools and nonvaccinated, infected control mice. One of the protective clone pools was further partitioned into 10 clone arrays of 108 clones each, and four clone arrays provided significant protection from both spleen and mesenteric lymph node colonization by M. avium subsp. paratuberculosis. The nucleotide sequence of each clone present in the protective pools was determined, and coding region functions were predicted by computer analysis. Comparison of the protective clone array sequences implicated 26 antigens that may be responsible for protection in mice. This study is the first study to demonstrate protection against M. avium subsp. paratuberculosis infection with expression library immunization.