Pierwsze biskupstwo (Ikosim, Icosium) na terenie dzisiejszej archidiecezji algierskiej powstało w II wieku wraz z ekspansją chrześcijaństwa na zachód. W tym czasie dochodziło do prześladowań wiernych tej religii ze strony władz Imperium Rzymskiego. Działo się tak aż do 313, kiedy to cesarzKonstantyn Wielki wydał tzw. edykt mediolański, który wprowadził równouprawnienie religijne dla chrześcijan. Diecezja ta została zlikwidowana w V wieku wraz z najazdami barbarzyńców na północno-zachodnią Afrykę. Została ona przywrócona wraz z podbojem tych ziem przez cesarza bizantyjskiegoJustyniana w 534. Wraz z podbojem Maghrebu przez Arabów i przymusowej islamizacji biskupstwo ponownie uległo likwidacji w 710[1].
25 lipca 1866 papież Pius IX wydzielił z terytorium biskupstwa dwie mniejsze diecezje: orańska oraz konstantynowską. Dotychczasową diecezję Iulia Caesarea przemianowano oficjalnie na algierską i podniesioną do rangi archidiecezji, ustanawiając ją ponadto metropolią. W 1905 w archidiecezji istniało 108 parafii, a katolicy stanowili 11% ogółu ludności (350 tysięcy) w 1959, jednak w wyniku masowej emigracji katolików z Algierii, która spowodowana była wojną o niepodległość, wywalczoną w 1962 liczba ta drastycznie spadła[3].
W 2012 urzędnicy kurii archidiecezjalnej ocenili, że z żyjących w archidiecezji katolików regularnie w mszach świętych uczestniczy jedynie 50 z nich[4].