Abstract Background Men in sub-Saharan Africa are less likely than women to get tested for HIV, less likely to present for treatment, less likely to be maintained in treatment, more likely to have detectable viral load, more likely to transmit HIV with unprotected intercourse, and more likely to progress to AIDS and die sooner from HIV. The ultimate objective of this research is to provide evidence-based strategies to improve HIV testing and treatment of HIV-infected men. Methods This study is being conducted in the Greater Edendale Area and Vulindlela region in KwaZulu-Natal, South Africa. It is a two-stage design of a cluster-randomized trial and an individual randomized trial to test how structural and individual-level interventions address the demand-side factors that affect HIV testing and treatment for hard-to reach, high-risk men. It combines male-focused mobilization, community-based mobile HIV testing services, and a small incentive to determine if the strategies singly and in combination can result in more men diagnosed with HIV, and more men linked to and maintained in care with undetectable viral load. Discussion A priority for sub-Sahara Africa is developing and evaluating novel and cost-effective strategies for identifying hard-to-reach groups such as men, linking them to HIV testing and care services, and maintaining them in care to the point of viral suppression. We propose a combination prevention intervention that addresses men’s individual, interpersonal, and structural barriers to testing and care. This includes male-led mobilization to encourage uptake of testing and treatment, male-focused testing venues, male-only counselors, developing counseling models that are flexible and responsive to men, and strategies for adhering to clinic visits without missing work and navigating the healthcare system. By thoughtfully combining male-focused mobilization, and testing and addressing some of the barriers to male engagement with health facilities, this study hopes to add to the growing evidence base about how to reach, test, link, and maintain a hard-to-reach group such as men in HIV treatment and care services. Trial registration ClinicalTrials.gov, NCT03794245. Registered on 4 January 2019.