Our aim was to describe the association between increasing access to antiretroviral therapy and all-cause mortality in South Africa from 2005 to 2009. We undertook a longitudinal, population-level study, using antiretroviral monitoring data reported by PEPFAR implementing partners and province-level and national all-cause mortality records from Statistics South Africa (provider of official South African government statistics) to analyse the association between antiretroviral treatment and mortality. Using mixed effects models with a random intercept for province, we estimated the contemporaneous and lagging association between antiretroviral treatment and all-cause mortality in South Africa. We also conducted subgroup analyses and estimated the number of deaths averted. For each 100 HIV-infected individuals on antiretroviral therapy reported by PEPFAR implementing partners in South African treatment programs, there was an associated 2.9 fewer deaths that year (95% CI: 1.5, 4.2) and 6.3 fewer deaths the following year (95% CI: 4.6, 8.0). The associated decrease in mortality the year after treatment reporting was seen in both adults and children, and men and women. Treatment provided from 2005 to 2008 was associated with 28,305 deaths averted from 2006 to 2009. The scale-up of antiretroviral treatment in South Africa was associated with a significant reduction in national all-cause mortality.