BACKGROUND: Men in sub-Saharan Africa have lower engagement and retention in HIV services compared to women, which may result in differential survival. However, the true magnitude of difference in HIV-related mortality between men and women receiving antiretroviral therapy (ART) is incompletely characterized. METHODS AND FINDINGS: We evaluated HIV-positive adults ≥18 years old newly initiating ART in 4 Zambian provinces (Eastern, Lusaka, Southern, and Western). In addition to mortality data obtained from routine electronic medical records, we intensively traced a random sample of patients lost to follow-up (LTFU) and incorporated tracing outcomes through inverse probability weights. Sex-specific mortality rates and rate differences were determined using Poisson regression. Parametric g-computation was used to estimate adjusted mortality rates by sex and age. The study included 49,129 adults newly initiated on ART between August 2013 and July 2015; overall, the median age among patients was 35 years, the median baseline CD4 count was 262 cells/μl, and 37.2% were men. Men comprised a smaller proportion of individuals starting ART (37.2% versus 62.8%), tended to be older (median age 37 versus 33 years), and tended to have lower CD4 counts (median 220 versus 289 cells/μl) at the time of ART initiation compared to women. The overall rate of mortality among men was 10.3 (95% CI 8.2-12.4) deaths/100 person-years (PYs), compared to 5.5 (95% CI 4.3-6.8) deaths/100 PYs among women (difference +4.7 [95% CI 2.3-7.2] deaths/100 PYs; p < 0.001). Compared to women in the same age groups, men's mortality rates were particularly elevated among those <30 years old (+6.7 deaths/100 PYs difference), those attending rural health centers (+9.4 deaths/100 PYs difference), those who had an initial CD4 count < 100 cells/μl (+9.2 deaths/100 PYs difference), and those who were unmarried (+8.0 deaths/100 PYs difference). After adjustment for potential confounders and mediators including CD4 count, a substantially higher mortality rate was predicted among men <30 years old compared to women of the same age, while women ≥50 years old had a mortality rate similar to that of age-matched men, but considerably higher than that predicted among young women (<30 years old). No clinically significant differences were evident with respect to rates of facility transfer or care disengagement between men and women. The main study limitations were the inability to successfully ascertain outcomes in all patients selected for tracing and missing clinical and laboratory data due to the use of medical records. CONCLUSIONS: In this study, we found that among HIV-positive adults newly initiating ART, mortality among men exceeded mortality among women; disparities were most pronounced among young patients. Older women, however, also experienced high mortality. Specific interventions for men and older women at highest mortality risk are needed to improve HIV treatment outcomes.