BACKGROUND: A small but significant number of patients do not achieve CD4 T-cell counts >500 cells/microl despite years of suppressive cART. These patients remain at risk of AIDS and non-AIDS defining illnesses. The aim of this study was to identify clinical factors associated with CD4 T-cell recovery following long-term cART. METHODS: Patients with the following inclusion criteria were selected from the Australian HIV Observational Database (AHOD): cART as their first regimen initiated at CD4 T-cell count 500 cells/microl and >200 cells/microl. RESULTS: 501 patients were eligible for inclusion from AHOD (n = 2853). The median (IQR) age and baseline CD4 T-cell counts were 39 (32-47) years and 236 (130-350) cells/microl, respectively. A major strength of this study is the long follow-up duration, median (IQR) = 6.5(3-10) years. Most patients (80%) achieved CD4 T-cell counts >500 cells/microl, but in 8%, this took >5 years. Among the patients who failed to reach a CD4 T-cell count >500 cells/microl, 16% received cART for >10 years. In a multivariate analysis, faster time to achieve a CD4 T-cell count >500 cells/microl was associated with higher baseline CD4 T-cell counts (p<0.001), younger age (p = 0.019) and treatment initiation with a protease inhibitor (PI)-based regimen (vs. non-nucleoside reverse transcriptase inhibitor, NNRTI; p = 0.043). Factors associated with achieving CD4 T-cell counts >200 cells/microl included higher baseline CD4 T-cell count (p<0.001), not having a prior AIDS-defining illness (p = 0.018) and higher baseline HIV RNA (p<0.001). CONCLUSION: The time taken to achieve a CD4 T-cell count >500 cells/microl despite long-term cART is prolonged in a subset of patients in AHOD. Starting cART early with a PI-based regimen (vs. NNRTI-based regimen) is associated with more rapid recovery of a CD4 T-cell count >500 cells/microl.