Background Although the success of HIV treatment programs depends on retention and viral suppression, routine program monitoring of these outcomes may be incomplete. We used data from the national electronic medical record (EMR) system in Zambia to enumerate a large and regionally representative cohort of patients on treatment. We traced a random sample with unknown outcomes (lost to follow-up) to document true care status and HIV RNA levels. Methods and findings On 31 July 2015, we selected facilities from 4 provinces in 12 joint strata defined by facility type and province with probability proportional to size. In each facility, we enumerated adults with at least 1 clinical encounter after treatment initiation in the previous 24 months. From this cohort, we identified lost-to-follow-up patients (defined as 90 or more days late for their last appointment), selected a random sample, and intensively reviewed their records and traced them via phone calls and in-person visits in the community. In 1 of 4 provinces, we also collected dried blood spots (DBSs) for plasma HIV RNA testing. We used inverse probability weights to incorporate sampling outcomes into Aalen–Johansen and Cox proportional hazards regression to estimate retention and viremia. We used a bias analysis approach to correct for the known inaccuracy of plasma HIV RNA levels obtained from DBSs. From a total of 64 facilities with 165,464 adults on ART, we selected 32 facilities with 104,966 patients, of whom 17,602 (17%) were lost to follow-up: Those lost to follow-up had median age 36 years, 60% were female (N = 11,241), they had median enrollment CD4 count of 220 cells/μl, and 38% had WHO stage 1 clinical disease (N = 10,690). We traced 2,892 (16%) and found updated outcomes for 2,163 (75%): 412 (19%) had died, 836 (39%) were alive and in care at their original clinic, 457 (21%) had transferred to a new clinic, 255 (12%) were alive and out of care, and 203 (9%) were alive but we were unable to determine care status. Estimates using data from the EMR only suggested that 42.7% (95% CI 38.0%–47.1%) of new ART starters and 72.3% (95% CI 71.8%–73.0%) of all ART users were retained at 2 years. After incorporating updated data through tracing, we found that 77.3% (95% CI 70.5%–84.0%) of new initiates and 91.2% (95% CI 90.5%–91.8%) of all ART users were retained (at original clinic or transferred), indicating that routine program data underestimated retention in care markedly. In Lusaka Province, HIV RNA levels greater than or equal to 1,000 copies/ml were present in 18.1% (95% CI 14.0%–22.3%) of patients in care, 71.3% (95% CI 58.2%–84.4%) of lost patients, and 24.7% (95% CI 21.0%–29.3%). The main study limitations were imperfect response rates and the use of self-reported care status. Conclusions In this region of Zambia, routine program data underestimated retention, and the point prevalence of unsuppressed HIV RNA was high when lost patients were accounted for. Viremia was prevalent among patients who unofficially transferred: Sustained engagement remains a challenge among HIV patients in Zambia, and targeted sampling is an effective strategy to identify such gaps in the care cascade and monitor programmatic progress.