© 2016, The Author(s). Male partner involvement has the potential to increase uptake of interventions to prevent mother-to-child transmission of HIV (PMTCT). Finding cultural appropriate strategies to promote male partner involvement in PMTCT programs remains an abiding public health challenge. We assessed whether a congregation-based intervention, the Healthy Beginning Initiative (HBI), would lead to increased uptake of HIV testing among male partners of pregnant women during pregnancy. A cluster-randomized controlled trial of forty churches in Southeastern Nigeria randomly assigned to either the HBI (intervention group; IG) or standard of care referral to a health facility (control group; CG) was conducted. Participants in the IG received education and were offered onsite HIV testing. Overall, 2498 male partners enrolled and participated, a participation rate of 88.9%. Results showed that male partners in the IG were 12 times more likely to have had an HIV test compared to male partners of pregnant women in the CG (CG = 37.71% vs. IG = 84.00%; adjusted odds ratio = 11.9; p < .01). Culturally appropriate and community-based interventions can be effective in increasing HIV testing and counseling among male partners of pregnant women.