This article examines some of the pertinent challenges arising out of personal experiences encountered through teaching religion and theology within an African environment. What the author describes as the "new Africa" in his title is a continent that has transitioned from slavery and colonialism into a global fraternity of democratic governance, access to wealth, sophisticated media technologies. In addition, the rise of new religious movements of both Christian and non-Christian persuasions following political and economic liberalizations and media explosion in Africa has been phenomenal. The author added that the rise of African migrant churches in the Diaspora has emerged as an important field of study and all indications are that the relationship between religious globalization and Religious Education may be more complex than people think.