Within Mozambique's current HIV care system, there are numerous opportunities for a person to become lost to follow-up (LTFU) prior to initiating antiretroviral therapy (pre-ART). We explored pre-ART LTFU in Zambézia province utilizing quantitative and qualitative methods. Patients were deemed LTFU if they were more than 60 days late for either a scheduled appointment or a CD4+ cell count blood draw, according to national guidelines. Among 13,968 adult patients registered for care, 211 (1.8 %) died, one transferred, 2,196 (15.7 %) initiated ART, and 9,195 (65.8 %) were LTFU during the first year. Being male, younger, less educated, and/or having no home electricity were associated with LTFU. Qualitative interviews revealed that poor clinical care, logistics and competing priorities contribute to attrition. In addition, many expressed fears of stigma and/or rejection by family or community members because they were HIV-infected. At 66 %, pre-ART LTFU in Zambézia, Mozambique is a significant problem. This study highlights characteristics of lost patients and discusses barriers requiring consideration to improve retention.