Introduction: Major depressive disorder, highly prevalent among people with HIV (PWH) globally, including South Africa, is associated with suboptimal adherence to antiretroviral therapy. Globally, there are insufficient numbers of mental health providers and tested depression treatments. This study's aim was to test task-shared cognitive-behavioural therapy for adherence and depression (CBT-AD) in HIV, delivered by clinic nurses in South Africa. Methods: This was a two-arm randomized controlled effectiveness trial (recruitment: 14 July 2016 to 4 June 2019, last follow 9 June 2020). One-hundred-sixty-one participants with clinical depression and virally uncontrolled HIV were recruited from primary care clinics providing HIV care, in Khayelitsha, South Africa. Arm 1 was task-shared, nurse-delivered CBT-AD; and arm 2 was enhanced treatment as usual (ETAU). Primary outcomes (baseline to 4 months) were blinded Hamilton Depression Rating Scale (HAM-D) scores, and weekly adherence via real-time monitoring (Wisepill). Secondary outcomes were adherence and depression over 4-, 8- and 12-month follow-ups, proportion of participants with undetectable viremia and continuous CD4 cell counts at 12 months. Additional analyses involved viral load and CD4 over time. Results: At 4 months, the HAMD scores in the CBT-AD condition improved by an estimated 4.88 points more (CI: –7.86, –1.87, p = 0.0016), and for weekly adherence, 1.61 percentage points more per week (CI: 0.64, 2.58, p = 0.001) than ETAU. Over follow-ups, CBT-AD had an estimated 5.63 lower HAMD scores (CI: –7.90, –3.36, p < 0.001) and 23.56 percentage points higher adherence (CI: 10.51, 34.21, p < 0.001) than ETAU. At 12 months, adjusted models indicated that the odds of having an undetectable viremia was 2.51 greater at 12 months (CI: 1.01, 6.66, p = 0.047), and 3.54 greater over all of the follow-ups (aOR = 3.54, CI: 1.59, 20.50; p = 0.038) for those assigned CBT-AD. CD4 was not significantly different between groups at 12 months or over time. Conclusions: Task-shared, nurse-delivered, CBT-AD is effective in improving clinical depression, ART adherence and viral load for virally unsuppressed PWH. The strategy of reducing depression to allow patients with self-care components of medical illness to benefit from adherence interventions is one to extend. Implementation science trials and analyses of cost-effectiveness are needed to translate findings into clinical practice. Trial Registration: ClinicalTrials.gov Identifier: NCT02696824 https://clinicaltrials.gov/ct2/show/NCT02696824.