Knowledge of immune mechanisms responsible for the cross-protection between highly divergent viruses such as human immunodeficiency virus type 1 (HIV-1) and HIV-2 may contribute to an understanding of whether virus variability may be overcome in the design of vaccine candidates which are broadly protective across the HIV subtypes. We demonstrate that despite the significant difference in virus amino acid sequence, the majority of HIV-2-infected individuals with different HLA molecules possess a dominant cytotoxic T-cell response which is able to recognize HIV-1 Gag protein. Furthermore, HLA-B5801-positive subjects show broad cross-recognition of HIV-1 subtypes since they mounted a T-cell response that tolerated extensive amino acid substitutions within HLA-B5801-restricted HIV-1 and HIV-2 epitopes. These results suggests that HLA-B5801-positive HIV-2-infected individuals have an enhanced ability to react with HIV-1 that could play a role in cross-protection.