BACKGROUND: Health education interventions tailored to suit men have the potential to improve health outcomes for this underserved population. HIV self-testing (HIVST) is a promising approach to overcoming challenges associated with low HIV testing rates among men. The primary objective of this study is to assess the feasibility of conducting a definitive trial to determine the effectiveness of a locally adapted and optimized health education program (HEP) on the uptake of HIVST among men in Kigali, Rwanda. METHODS: This study employs a pilot pragmatic randomized controlled trial to evaluate an HIVST HEP for men. Participants were randomized to the intervention (HEP) arm or to the control arm. In the intervention group, the adapted HEP was administered in addition to routine health education. In the non-intervention group, only routine health education was offered. Participant data was collected first upon recruitment and then after 3 months’ follow-up using interviewer-administered questionnaires. RESULTS: There was a 100% response rate at enrollment and no loss to follow-up at exit. There was significant association between the study arm and knowledge of HIVST. Participants in the control arm had a mean knowledge score of 67% compared to 92% among participants in the intervention arm. There was an association between the study arm and HIVST uptake: 67% of the study participants in the intervention arm self-reported HIVST uptake compared to 23% of the participants in the control arm. DISCUSSION: This pilot study demonstrates the feasibility of a larger trial to assess the effectiveness of an HEP intervention on uptake of HIVST among men. We found preliminary evidence of increased uptake of HIVST in the intervention group.