Plasmodium vivax merozoite surface protein (PvMSP9) stimulates both cellular and humoral immune responses in individuals who are naturally infected by this parasite species. To identify immunodominant human T-cell epitopes in PvMSP9, we used the MHC class II binding peptide prediction algorithm ProPred. Eleven synthetic peptides representing predicted putative promiscuous T cell epitopes were tested in IFN-γ and IL-4 ELISPOT assays using peripheral blood mononuclear cells (PBMC) derived from 142 individuals from Rondonia State, Brazil who had been naturally exposed to P. vivax infections. To determine whether the predicted epitopes are preferentially recognized in the context of multiple alleles, MHC Class II typing of the cohort was also performed. Five synthetic peptides elicited robust cellular responses, and the overall frequencies of IFN-γ and IL-4 responders to at least one of the promiscuous peptides were 62% and 46%, respectively. The frequencies of IFN-γ and IL-4 responders to each peptide were not associated with a particular HLA-DRB1 allelic group since most of the peptides induced a response in individuals of 12 out of 13 studied allelic groups. The prediction of promiscuous epitopes using ProPred led to the identification of immunodominant epitopes recognized by PBMC from a significant proportion of a genetically heterogeneous population exposed to malaria infections. The combination of several such T-cell epitopes in a vaccine construct may increase the frequency of responders and the overall efficacy of subunit vaccines in genetically distinct populations.