In Kenyan communities, religious leaders are important gatekeepers in matters of health and public morality. In a context that is generally homophobic, religious leaders may aggravate or reduce stigmatization of sexual minorities such as gay and bisexual men, and other men who have sex with men (GBMSM). Literature indicates mixed results in efforts to encourage religious leaders to work effectively and sensitively with issues regarding HIV and sexuality. This paper describes the implementation of an engagement intervention with religious leaders from different denominations, which took place following a homophobic hate attack that was led by local religious leaders, at an HIV research clinic for GBMSM on the Kenyan coast. After the homophobic attack, tailored engagement activities, including a comprehensive four-day online sensitivity training course took place between June 2015 and October 2016 in the Kenyan coast. HIV researchers, together with trained GBMSM activists, organized the series of engagement activities for religious leaders which unfolded iteratively, with each subsequent activity informed by the results of the previous one. Facilitated conversations were used to explore differences and disagreements in relation to questions of scripture, mission, HIV, and human sexuality. As a result, researchers noted that many religious leaders, who initially expressed exceedingly negative attitudes towards GBMSM, started to express far more accepting and supportive views of sexuality, sexual identities, and same-sex relations. This paper describes the changes in religious leaders’ discourses relating to GBMSM, and highlights the possibility of using engagement interventions to build trust between research institutes, religious leaders, and GBMSM.