Despite the importance of vaccinia virus in basic and applied immunology, our knowledge of the human immune response directed against this virus is very limited. CD4(+) T cell responses are an important component of immunity induced by current vaccinia-based vaccines, and likely will be required for new subunit vaccine approaches, but to date vaccinia-specific CD4(+) T cell responses have been poorly characterized, and CD4(+) T cell epitopes have been reported only recently. Classical approaches used to identify T cell epitopes are not practical for large genomes like vaccinia. We developed and validated a highly efficient computational approach that combines prediction of class II MHC-peptide binding activity with prediction of antigen processing and presentation. Using this approach and screening only 36 peptides, we identified 25 epitopes recognized by T cells from vaccinia-immune individuals. Although the predictions were made for HLA-DR1, eight of the peptides were recognized by donors of multiple haplotypes. T cell responses were observed in samples of peripheral blood obtained many years after primary vaccination, and were amplified after booster immunization. Peptides recognized by multiple donors are highly conserved across the poxvirus family, including variola, the causative agent of smallpox, and may be useful in development of a new generation of smallpox vaccines and in the analysis of the immune response elicited to vaccinia virus. Moreover, the epitope identification approach developed here should find application to other large-genome pathogens.