The HIV-1 regulatory proteins Tat and Rev and the accessory proteins Vpr, Vpu and Vif are essential for efficient viral replication, and their cytoplasmic production suggests that they should be processed for recognition by cytotoxic T lymphocytes. However, only limited data is available, evaluating the role of immune responses directed against these proteins in natural HIV-1 infection. Recent advances in the methods used for the characterization of HIV-1-specific cellular immune responses, including quantification of antigen-specific IFN-γ production by ELISpot assay and flow-cytometry-based intracellular cytokine quantification, have allowed for a much more comprehensive assessment of virus-specific immune responses. Emerging data show that the regulatory and accessory proteins serve as important targets for HIV-1-specific T cell responses, and multiple CTL epitopes have been identified in functionally important regions of these proteins. Moreover, the use of autologous peptides have allowed for the detection of significantly stronger HIV-1-specific T cell responses in the more variable regulatory and accessory HIV-1 proteins Tat and Vpr. These data indicate that despite the small size of these proteins, regulatory and accessory proteins are targeted by cellular immune responses in natural HIV-1 infection and contribute importantly to the total HIV-1-specific CD8+ T cell response. A multi-component vaccine, with the inclusion of these proteins plus structural proteins remains the most promising choice for an effective AIDS vaccine.