In the predominantly Muslim context of Zanzibar, Pentecostal Christianity is slowly on the rise as a result of an influx of labor migrants from mainland Tanzania. A paramount feature in these churches is the provision of divine healing and deliverance from spiritual affliction. This article analyses how narratives of healing in one of Zanzibar’s major Pentecostal churches, the City Christian Center, influence how religious belonging is negotiated and manifested. Focusing on Zanzibar-born Pentecostals with Roman Catholic backgrounds, the analysis suggests that healing and practices conducted to deliver individuals from pain and suffering are connected to a wider revaluation of moral and social actions characterizing Zanzibar society. It stresses that Pentecostal belonging builds on Zanzibar-born members’ previous experiences of Zanzibar in a process of both affirmation and rejection, in which adherence to Christianity is intensified by an increased knowledge of God’s power to heal, and opposition to the Muslim majority is strengthened by connecting it to sickness.