Abstract Background The mitochondrial DNA (mtDNA) seems to influence in a large number of diseases, including HIV infection. Moreover, there is a substantial inter-individual variability in the CD4+ recovery in HIV-infected patients on combination antiretroviral therapy (cART). Our study aimed to analyze the association between mtDNA haplogroups and CD4+ recovery in HIV-infected patients on cART. Methods This is a retrospective study of 324 naïve cART patients with CD4+ 9.65 CD4+ cells/mm3/month) than patients without haplogroup H (p = 0.032). The adjusted logistic regression showed that patients carrying haplogroup H had a higher likelihood of achieving a CD4+ recovery > 9.65 CD4+ cells/mm3/month [adjusted odds ratio (aOR) = 1.75 (95% CI = 1.04; 2.95); p = 0.035]. Conclusions European mitochondrial haplogroup H was associated with the improved CD4+ recovery in HIV-infected patients starting cART with CD4+ < 200 cells/mm3.