Abstract: Background: A considerable portion of the HIV pandemic is composed of people under antiretroviral therapy, many of whom get a late diagnosis. Patients starting antiretroviral therapy (ART) at a very advanced stage of HIV disease attain a low recovery of CD4 T cells. Factors associated with poor recovery are incompletely described. This study aimed at finding variables associated with CD4 T cell recovery in late-presenting HIV patients. Methods: We studied a cohort of HIV+ patients initiating ART with very low basal CD4 T cell counts. We defined immune recovery as the net increase in circulating CD4 T cell counts after one year on ART. We analyzed diverse routine laboratory determinations at different times using Least Absolute Shrinkage and Selection Operator (LASSO), adaptive LASSO and Conditional Inference Random Forest. Results: CD4/CD8 ratio, % CD4 T cells and CD8 T cell counts at different times were the main recovery correlates, validated by all approaches. Unexpectedly, basal hematocrit was a consistent predictor. Additionally, week 24 creatinine had a high lasso coefficient, and alkaline phosphatase had a high conditional inference random forest coefficients, although neither was verified by other tests. Conclusions: CD4 T cell proportions are associated with CD4 T cell recovery, independently of cell counts. Inflammation-related variables could also affect reconstitution. These accessible variables may reflect underlying mechanisms and could improve the follow up of patients starting ART with an advanced HIV infection.