Background In resource-limited settings, many HIV-infected patients are lost to follow-up (LTF) before starting ART; risk factors among those not eligible for ART at enrollment into care are not well described. Methods We examined data from 4,278 adults (3,613 women, 665 men) enrolled in HIV care through March 2007 in the MTCT-Plus Initiative with a CD4 count ≥200 cells/mm3 and WHO stage ≤ 2 at enrollment. Patients were considered LTF if > 12 months elapsed since their last clinic visit. Gender-specific Cox regression models were used to assess LTF risk factors. Results The proportion LTF was 8.2 % at 12 months following enrollment, and was higher among women (8.4 %) than men (7.1 %). Among women, a higher risk of LTF was associated with younger age (adjusted hazard ratio [AHR]15–19/30+: 2.8, 95 % CI:2.1-3.6; AHR20–24/30+:1.9, 95 % CI:1.7-2.2), higher baseline CD4 count (AHR350–499/200–349:1.5; 95 % CI:1.0-2.1; AHR500+/200–349:1.5; 95 % CI:1.0-2.0), and being pregnant at the last clinic visit (AHR:1.9, 95 % CI:1.4-2.5). Factors associated with a lower risk of LTF included, employment outside the home (AHR:0.73, 95 % CI:0.59-0.90), co-enrollment of a family/household member (AHR:0.40, 95 % CI:0.26-0.61), and living in a household with ≥4 people (AHR:0.74, 95 % CI:0.64-0.85). Among men, younger age (AHR15–19/30+: 2.1, 95 % CI:1.2-3.5 and AHR30–34/35+:1.5, 95 % CI:1.0-2.4) had a higher risk of LTF. Electricity in the home (AHR:0.61, 95 % CI:0.41-0.91) and living in a household with ≥4 people (AHR:0.58, 95 % CI:0.39-0.85) had a lower risk of LTF. Conclusions Socio-economic status and social support may be important determinants of retention in patients not yet eligible for ART. Among women of child-bearing age, strategies around sustaining HIV care during and after pregnancy require attention.