MHC-I-restricted cytotoxic responses are considered a critical component of protective immunity against viruses, including human immunodeficiency virus type 1 (HIV-1). CTLs directed against accessory and early regulatory HIV-1 proteins might be particularly effective; however, CTL epitopes in these proteins are rarely found. Novel artificial neural networks (ANNs) were used to quantitatively predict HLA-A2-binding CTL epitope peptides from publicly available full-length HIV-1 protein sequences. Epitopes were selected based on their novelty, predicted HLA-A2-binding affinity and conservation among HIV-1 strains. HLA-A2 binding was validated experimentally and binders were tested for their ability to induce CTL and IFN-gamma responses. About 69 % were immunogenic in HLA-A2 transgenic mice and 61 % were recognized by CD8(+) T-cells from 17 HLA-A2 HIV-1-positive patients. Thus, 31 novel conserved CTL epitopes were identified in eight HIV-1 proteins, including the first HLA-A2 minimal epitopes ever reported in the accessory and regulatory proteins Vif, Vpu and Rev. Interestingly, intermediate-binding peptides of low or no immunogenicity (i.e. subdominant epitopes) were found to be antigenic and more conserved. Such epitope peptides were anchor-optimized to improve immunogenicity and further increase the number of potential vaccine epitopes. About 67 % of anchor-optimized vaccine epitopes induced immune responses against the corresponding non-immunogenic naturally occurring epitopes. This study demonstrates the potency of ANNs for identifying putative virus CTL epitopes, and the new HIV-1 CTL epitopes identified should have significant implications for HIV-1 vaccine development. As a novel vaccine approach, it is proposed to increase the coverage of HIV variants by including multiple anchor-optimized variants of the more conserved subdominant epitopes.