Introduction: In April 2010, tenofovir replaced stavudine in public-sector first-line antiretroviral therapy (ART) in South Africa. The association of tenofovir with fewer side effects and toxicities compared to stavudine could translate to increased durability of tenofovir-based regimens. We evaluated changes over time in regimen durability at the Themba Lethu Clinic, Johannesburg, South Africa. Methods: This was a cohort analysis of treatment-naïve, non-pregnant adult patients initiated on ART between April 2004 and December 2011. First-line ART regimens before April 2010 consisted of stavudine or zidovudine with lamivudine and either efavirenz or nevirapine. Tenofovir was substituted for stavudine after April 2010. We evaluated the frequency and type of single-drug substitutions (excluding switches to second-line therapy). Cox models were used to evaluate the association of ART initiation year and antiretroviral drug type with single-drug substitutions in the first 12 months on treatment. Results: One thousand nine hundred and sixty-four (10%) substitutions occurred amongst 19,699 patients. Excluding 2004 (year of treatment roll-out), before 2010 one-year single-drug substitutions ranged from 10.0 to 13.1%. In 2011, well after integration of tenofovir, substitutions decreased to 5.6%. Single-drug substitution was lowest amongst patients on tenofovir (5.1%) versus zidovudine (11.3%), 30 mg stavudine (10.5%) or 40 mg stavudine (14.4%). Adjusted Cox models showed that patients initiating treatment between 2005 and 2010 (vs. 2011) had a twofold increased hazard of single-drug substitution, while those on zidovudine or stavudine had a two to threefold increase in single-drug substitution versus tenofovir patients in the first 12 months on ART. Conclusions: The decline in single-drug substitutions is associated with the introduction of tenofovir. Tenofovir use could improve regimen durability and treatment outcomes in resource-limited settings.