This paper initiates a novel discourse advocating for the anti-colonization of religious education (RE) in Africa South of the Sahara (ASoS). It illustrates how anti-colonial critiques can not only offer more precise theoretical perspectives but also generate a practical imperative for a paradigm shift in a school subject "still" influenced by what I have labeled as the neocoloniality of power. In some countries, attempts to decolonize RE through multi-faithism are being forsaken, reverting the subject to the Christonormativity of the colonial era. The paper contends that the process of reconceptualizing RE with an anti-colonial mindset should inspire innovative ideas for an anti-colonized RE aligned with the educational goals in an African postcolonial environment.