© 2018 Holmes et al. Background: Survival represents the single most important indicator of successful HIV treatment. Routine monitoring fails to capture most deaths. As a result, both regional assessments of the impact of HIV services and identification of hotspots for improvement efforts are limited. We sought to assess true mortality on treatment, characterize the extent under-reporting of mortality in routine health information systems in Zambia, and identify drivers of mortality across sites and over time using a multistage, regionally representative sampling approach. Methods and findings: We enumerated all HIV infected adults on antiretroviral therapy (ART) who visited any one of 64 facilities across 4 provinces in Zambia during the 24-month period from 1 August 2013 to 31 July 2015. We identified a probability sample of patients who were lost to follow-up through selecting facilities probability proportional to size and then a simple random sample of lost patients. Outcomes among patients lost to follow-up were incorporated into survival analysis and multivariate regression through probability weights. Of 165,464 individuals (64% female, median age 39 years (IQR 33–46), median CD4 201 cells/mm3(IQR 111–312), the 2-year cumulative incidence of mortality increased from 1.9% (95% CI 1.7%–2.0%) to a corrected rate of 7.0% (95% CI 5.7%–8.4%) (all ART users) and from 2.1% (95% CI 1.8%–2.4%) to 8.3% (95% CI 6.1%–10.7%) (new ART users). Revised provincial mortality rates ranged from 3–9 times higher than naïve rates for new ART users and were lowest in Lusaka Province (4.6 per 100 person-years) and highest in Western Province (8.7 per 100 person-years) after correction. Corrected mortality rates varied markedly by clinic, with an IQR of 3.5 to 7.5 deaths per 100 person-years and a high of 13.4 deaths per 100 person-years among new ART users, even after adjustment for clinical (e.g., pretherapy CD4) and contextual (e.g., province and clinic size) factors. Mortality rates (all ART users) were highest year 1 after treatment at 4.6/100 person-years (95% CI 3.9–5.5), 2.9/100 person-years (95% CI 2.1–3.9) in year 2, and approximately 1.6% per year through 8 years on treatment. In multivariate analysis, patient-level factors including male sex and pretherapy CD4 levels and WHO stage were associated with higher mortality among new ART users, while male sex and HIV disclosure were associated with mortality among all ART users. In both cases, being late (>14 days late for appointment) or lost (>90 days late for an appointment) was associated with deaths. We were unable to ascertain the vital status of about one-quarter of those lost and selected for tracing and did not adjudicate causes of death. Conclusions: HIV treatment in Zambia is not optimally effective. The high and sustained mortality rates and marked under-reporting of mortality at the provincial-level and unexplained heterogeneity between regions and sites suggest opportunities for the use of corrected mortality rates for quality improvement. A regionally representative sampling-based approach can bring gaps and opportunities for programs into clear epidemiological focus for local and global decision makers.