Two religious histories occupy the same ground here and are rarely discussed together.
The first is ancient and Christian. Roman North Africa was one of the intellectual centres of Latin Christianity. Augustine was bishop of Hippo, in what is now Annaba, and the Donatist controversy, which split the African church for a century over whether clergy who had handed over scriptures during persecution retained valid orders, was fought out in these provinces. The question it raised, whether the holiness of a sacrament depends on the holiness of the minister, was settled against the Donatists and shaped Western sacramental theology permanently. That church did not survive the Islamic period, and its disappearance is one of the genuinely unexplained problems of religious history.
The second is the Islam that followed, Sunni and Maliki, with two features that mark Algeria out. There is an Ibadi minority among the Mozabite Berbers of the Mzab valley, whose fortified oasis towns around Ghardaia are inscribed by UNESCO and whose community regulates its own affairs through religious councils, a form of Islam distinct from both Sunni and Shia and shared with Oman and the Libyan Nafusa. And there is a very strong marabout and Sufi inheritance, in which the Rahmaniyya order and the emir Abd al Qadir, himself the son of a Qadiriyya shaykh, led nineteenth century resistance to French conquest.
The civil war of the 1990s, set off by the annulment of elections the Islamic Salvation Front was winning, killed well over a hundred thousand people and shapes every subsequent religious policy in the country.