Innovative approaches are needed to increase engagement in HIV treatment and prevention services, particularly in HIV hot spots. Here, we detail our design, training approach, and early implementation experiences of a community-based HIV intervention called “health scouts.” The intervention, utilizing a novel, theory-based approach, trained 10 community residents in an HIV hot spot fishing community to use motivational interviewing strategies and a mobile phone-based counseling application. During the first 3 months, 771 residents (median 82/health scout, range 27-160) were counseled. A directly observed Motivational Interviewing Treatment Integrity scale-based evaluation found adequate performance (median score 20⁄25, range 11-23). The health scout intervention was feasible to implement in a high HIV-prevalence fishing community, and its impact on HIV care outcomes will be evaluated in an ongoing cluster randomized trial. If found to be effective, it may be an important strategy for responding to HIV in high-burden settings.