This chapter examines the multifaceted relations between religion and sexuality in African cultures and societies. First, it unpacks how sexuality is perceived in African indigenous religions, linked to beliefs in fertility, immortality and ancestors, and how such beliefs continue to shape contemporary religious concerns, both in Christianity and Islam. This section includes a feature about religious leaders offering penis enlargement services (!) and examines the rationale behind such concerns. Second, the chapter discusses traditional cultures of same-sex intimacy, and their links to religious beliefs and practices. The feature item here focuses on self-identifying lesbian sangomas (traditional healers) in Southern Africa. Third, the chapter draws attention to contemporary politics of sexuality, especially in relation to gay rights and the HIV epidemic. Throughout, the chapter argues that sexuality is one of the key sites manifesting the complex religious dynamics in post-colonial African societies vis-à-vis globalization and social change.