Using a pilot trial design in an HIV care clinic in Zimbabwe, we randomised 32 adults with poor adherence to antiretroviral therapy and at least mild depression to either six sessions of Problem-Solving Therapy for adherence and depression (PST-AD) delivered by an adherence counsellor, or to Enhanced Usual Care (Control). Acceptability of PST-AD was high, as indicated by frequency of session attendance and through qualitative analyses of exit interviews. Fidelity was >80% for the first two sessions of PST-AD but fidelity to the adherence component of PST-AD dropped by session 4. Contamination occurred, in that seven patients in the control arm received one or two PST-AD sessions before follow-up assessment. Routine health records proved unreliable for measuring HIV viral load at follow-up. Barriers to measuring adherence electronically included device failure and participant perception of being helped by the research device. The study was not powered to detect clinical differences, however, promising change at 6-months follow-up was seen in electronic adherence, viral load suppression (PST-AD arm 9/12 suppressed; control arm 4/8 suppressed) and depression (Patient Health Questionnaire-4.7 points in PST-AD arm vs. control, adjusted p value = 0.01). Results inform and justify a future randomised controlled trial of task-shifted PST-AD.