Increasing efforts are directed towards the development of effective vaccines through induction of virus-specific T cell responses. Although emerging data indicate a significant role of these cells in determining viral set point in infections such as HIV, there is as yet no consensus as to the best methods for assaying the breadth of these responses. In this study, we used sensitive interferon gamma-based intracellular cytokine staining (ICS) and Elispot assays to determine the optimal overlapping peptide set to screen for these responses. Twenty persons with established HIV infection were studied, focusing on responses to the highly immunogenic Nef protein. Six different HIV-1 Nef peptide sets were used, ranging in length from 15 to 20 amino acids (aa), in overlap from 10 to 11 amino acids, and derived from two different B clade sequences. A total of 54 CD8 T cell responses to Nef peptides were found in this cohort, of which only 12 were detected using previously defined Nef optimal epitopes. No single peptide set detected all responses. Though there was a trend of the shorter peptides detecting more CD8 T cell responses than the 20 amino acid long peptides and longer peptides detecting more CD4 T cell responses, neither was statistically significant. There was no difference between an overlap of 10 or 11 amino acids. All responses detected with the six different sets of overlapping peptides were towards the more highly conserved regions of Nef. We conclude that peptides ranging from 15 to 20 amino acids yield similar results in IFN-gamma-based Elispot and ICS assays, and that all are likely to underestimate the true breadth of responses to a given reference strain of virus.