Uptake of HIV testing is suboptimal in Uganda, particularly in rural communities. Reaching UNAIDS 95-95-95 goals requires strategies to increase HIV testing among hard-to-reach populations. This cross-sectional study sought to characterize engagement with HIV testing among traditional healers and their clients in rural Uganda. We enrolled 175 traditional healers and 392 adult clients of healers in Mbarara District. The primary outcome for this study was having received an HIV test in the prior 12 months. Most clients (n = 236, 65.9%) had received an HIV test within 12 months, compared to less than half of healers (n = 75, 46.3%) who had not. In multivariate regression models, male clients of healers were half as likely to have tested in the past year, compared with female (adjusted odds ratios (AORs) = 0.43, 95% CI = 0.26-0.70). Increasing age negatively predicted testing within the past year (AOR = 0.95, 95% CI = 0.93-0.97) for clients. Among healers, more sexual partners predicted knowing ones serostatus (AOR = 1.6, 95% CI 1.03-2.48). Healers (AOR = 1.16, 95% CI 1.07-1.26) and clients (AOR = 1.28, 95% CI 1.13-1.34 for clients) with greater numbers of lifetime HIV tests were more likely to have tested in the past year. Traditional healers and their clients lag behind UNAIDS benchmarks and would benefit from programs to increase HIV testing uptake.