Before the 2015 implementation of "Test and Start," the initiation of combination antiretroviral therapy (ART) was guided by specific CD4 cell count thresholds. As scale-up efforts progress, the prevalence of advanced HIV disease at ART initiation is expected to decline. We analyzed the temporal trends in the median CD4 cell counts among adults initiating ART and described factors associated with initiating ART with severe immunodeficiency in Zambézia Province, Mozambique. We included all HIV-positive, treatment-naive adults (age ≥ 15 years) who initiated ART at a Friends in Global Health (FGH)-supported health facility between September 2012 and September 2017. Quantile regression and multivariable logistic regression models were applied to ascertain the median change in CD4 cell count and odds of initiating ART with severe immunodeficiency, respectively. A total of 68,332 patients were included in the analyses. The median change in CD4 cell count under "Test and Start" was higher at +68 cells/mm (95% CI: 57.5-78.4) compared with older policies. Younger age and female sex (particularly those pregnant/lactating) were associated with higher median CD4 cell counts at ART initiation. Male sex, advanced age, WHO Stage 4 disease, and referrals to the health facility through inpatient provider-initiated testing and counseling (PITC) were associated with higher odds of initiating ART with severe immunodeficiency. Although there were reassuring trends in increasing median CD4 cell counts with ART initiation, ongoing efforts are needed that target universal HIV testing to ensure the early initiation of ART in men and older patients.