Following the introduction of highly active antiretroviral therapy (HAART), the incidence of Kaposi's sarcoma (KS) has significantly declined in human immunodeficiency virus type 1 (HIV-1)-positive (HIV-1+) individuals and clinical remission is often observed. We hypothesize that these effects are partly due to anti-KS-associated herpesvirus (KSHV) immune restoration. Here, 15-mer overlapping peptides from proteins K12 and K8.1 were used to identify novel KSHV-specific cytotoxic T-lymphocyte epitopes. Three immunogenic peptides, two lytic and one latent, were subsequently used to monitor the anti-KSHV CD8+ T-cell responses in a cohort of 19 HIV-1+ KSHV+/− KS+/− individuals during 52 weeks of HAART. KSHV and HIV-1 loads, KSHV antibody titers, and both CD4+ and CD8+ T-lymphocyte counts were enumerated. Prior to HAART, the total number of spot-forming cells (SFC) for all three peptides correlated with both CD4+ and CD8+ T-lymphocyte counts (P ≤ 0.05) in the KSHV-positive KS-positive cohort (n = 11). Following 52 weeks of HAART, significant decreases in HIV-1 and KSHV loads were associated with significant increases in CD4+ T-lymphocyte counts and number of SFC for the three KSHV-specific peptides. Although these increases were modest in comparison to the number of SFC observed with the HIV-1 gag peptide SLYNTVATL, they represented a fourfold increase from the baseline, continuing an upward trend to week 52.