Objectives: Stavudine is being phased out because of its mitochondrial toxicity and tenofovir (TDF) is recommended as part of first-line highly active antiretroviral therapy (HAART) in South Africa. A prospective, open-label, randomized controlled trial comparing standard- and low-dose stavudine with TDF was performed to assess early differences in adipocyte mtDNA copy number, gene expression and metabolic parameters in Black South African HIV-infected patients. Methods: Sixty patients were randomized 1:1:1 to either standard-dose (30–40 mg) or low-dose (20–30 mg) stavudine or TDF (300 mg) each combined with lamivudine and efavirenz. Subcutaneous fat biopsies were obtained at weeks 0 and 4. Adipocyte mtDNA copies/cell and gene expression were measured using quantitative polymerase chain reaction (qPCR). Markers of inflammation and lipid and glucose metabolism were also assessed. Results: A 29% and 32% decrease in the mean mtDNA copies/cell was noted in the standard-dose (P < 0.05) and low-dose stavudine (P < 0.005) arms, respectively, when compared with TDF at 4 weeks. Nuclear respiratory factor-1 (NRF1) and mitochondrial cytochrome B (MTCYB) gene expression levels were affected by stavudine, with a significantly (P < 0.05) greater fall in expression observed with the standard, but not the low dose compared with TDF. No significant differences were observed in markers of inflammation and lipid and glucose metabolism. Conclusions: These results demonstrate early mitochondrial depletion among Black South African patients receiving low and standard doses of stavudine, with preservation of gene expression levels, except for NRF1 and MTCYB, when compared with patients on TDF.