Collaborations with traditional healers have been proposed to improve HIV testing uptake. We hypothesized that healer-delivered HIV testing would improve HIV testing uptake, compared with referral to clinic-based HIV testing. We conducted a cluster randomized trial to determine the effectiveness of traditional healers delivering counseling and HIV testing in Mwanza, Tanzania (ClinicalTrials.gov NCT#04071873). Intervention arm healers provided counseling and offered point-of-care HIV tests to adult clients of unknown HIV serostatus. Control arm healers provided referral for clinic-based testing. Primary outcome was receipt of an HIV test within 90 days of enrollment. Secondary outcomes were new HIV diagnosis and linkage to care. In the intervention, 100 clients (100%) received an HIV test, compared with 73 (73%) of control participants (p < 0.001). Two intervention arm participants (2%) had a new diagnosis compared with zero in the control arm (p = 0.50). Engaging traditional healers might provide a culturally concordant opportunity to improve HIV testing uptake.