Background: West Nile virus (WNV) is a growing threat to public health and a greater understanding of the immune response raised against WNV is important for the development of prophylactic and therapeutic strategies. Methodology/Principal Findings: In a reverse-immunology approach, we used bioinformatics methods to predict WNV-specific CD8(+) T cell epitopes and selected a set of peptides that constitutes maximum coverage of 20 fully-sequenced WNV strains. We then tested these putative epitopes for cellular reactivity in a cohort of WNV-infected patients. We identified 26 new CD8(+) T cell epitopes, which we propose are restricted by 11 different HLA class I alleles. Aiming for optimal coverage of human populations, we suggest that 11 of these new WNV epitopes would be sufficient to cover from 48% to 93% of ethnic populations in various areas of the World. Conclusions/Significance: The 26 identified CD8(+) T cell epitopes contribute to our knowledge of the immune response against WNV infection and greatly extend the list of known WNV CD8(+) T cell epitopes. A polytope incorporating these and other epitopes could possibly serve as the basis for a WNV vaccine.