We compared the number/percentages of naive and memory CD4+ T-cells, CD38+ CD8+ T-cells, and CD28+ CD4+ and CD28+ CD8+ T-cells in patients with advanced HIV disease (baseline CD4+ count < 100) with those with less advanced (baseline CD4+ cell count > 100) HIV disease during 4 years of suppressive highly active antiretroviral therapy. This prospective, longitudinal study included 30 treatment-naive patients and 32 controls. Advanced HIV-infected patients (n = 13) gained more CD4+ T-cells than less advanced patients (n = 11) at 1 month (median: 60 vs. 36 microL(-1)), 3 months (86 vs. 14), 6 months (111 vs. 23), 12 months (174 vs. 47), 24 months (162 vs. 72) and 48 months (257 vs. 123) (P = 0.15, P < 0.001, P = 0.026, P = 0.021, P = 0.1 and P = 0.06, respectively). Advanced patients gained more naive CD4+ T-cells at 48 months compared to less advanced patients (27.3 vs. 11.4%, P = 0.05). The relative gain in memory CD4+ T-cells was greater in advanced vs. less advanced patients at 1 month (median: 6.4 vs. 1.4%), 3 months (4.3 vs. 2.0), 6 months (6.7 vs. 1.6), 12 months (6.9 vs. 2.4), 24 months (7.5 vs. 3.1) and 48 months (11.3 vs. 6.8) (P = 0.002, P = 0.013, P < 0.001, P = 0.004, P = 0.001 and P = 0.015, respectively). At 48 months, CD38+ CD8+ T-cells and naive CD4+ T-cells reached normal values (9.2%, P = 0.869 vs. controls and 47.5%, P = 0.699, respectively) in less advanced patients, as did CD38+ CD8+ T-cells in advanced patients (4.7%, P = 0.309 vs. controls). The kinetics of naive and memory CD4+ T-cell reconstitution is different in less advanced compared to advanced HIV patients.