
Le lieu est déjà habité par les Romains : une mosaïque représentant le triomphe d'Amphitrite est découverte en 1898 à 700 mètres à l'est de la ville et déposée au musée des Antiquités d'Alger. Selon les chroniqueurs arabes et notamment Ibn Hammad qui signale qu'il s'appelait château de Kiana mais aussi fort du Miroir, il sert de refuge à Abu Yazid (« l'homme à l'âne ») dans sa révolte contre les califes fatimides Al-Qaim et Al-Mansur.La Kalâa est fondée en 1007 par Hammad ibn Bologhine, fils de Bologhine ibn Ziri (fondateur d'Alger), qui obtient de son suzerain Badis, prince Ziride d'Ifriqiya, l'autorisation d'édifier une ville et d'en faire sa capitale. Il y engage durant deux ans de grands projets de construction. La position de la nouvelle citadelle présente des avantages stratégiques encore supérieurs à ceux d'Achir. Hammad s'empresse de la fortifier et, selon Ibn Khaldoun, de la peupler avec les habitants de Msila et de Hamza (Bouira) après avoir détruit leurs villes, ainsi que des Djerawa.

Les troupes zirides quittent alors la Kalâa. Hammad fait plus tard la paix avec le fils et successeur de Badis, Al-Muizz, qui doit se résigner au fait accompli (1017). Le mariage de Abdallah, fils de Hammad, et d'Umm al-Ulu, sœur d'Al-Muizz, marque l'alliance des deux princes. En 1185 Ali b Ghaniya y pénètre après un siège de trois jours.




Sous le règne d'Al-Qaid, les hostilités ayant repris entre les Zirides et les Hammadites, la Kalaâ est assiégée entre 1040 et 1042. Sous celui de An-Nasir, elle est conquise par Ali b. Raggam mais selon Ibn Khaldoun reprise rapidement. En 1090 Al-Mansur quitte la Kalâa, sous la menace hilalienne, pour s'installer à Béjaïa (Bougie) avec sa troupe et sa cour. Le déclin de la ville, jusque-là l'une des plus importantes du Maghreb central, commence sous le règne d'Al-Aziz (1105-1121).
Assiégée par les Hilaliens elle n'est sauvée que par l'intervention de l'armée envoyée de Bougie par le souverain. En 1148 Yahya, dernier prince hammadite (1121-1152), fait transporter à Bougie tous les objets de valeur de la ville. En 1152 elle est prise et en partie détruite par les troupes Almohades dirigées par Abdallah, fils du calife Abd al-Mumin. En 1185 l'almoravide Ali Ibn Ghaniya y pénètre après un siège de trois jours. L'emplacement de la capitale des Hammadides est resté vierge de toute autre construction depuis le Moyen Âge. Les premières fouilles conduites par Paul Blanchet en avril 1897 ont pour objet le donjon du Manar. Le général Léon de Beylié poursuit en 1908 le dégagement du palais du Lac et de la grande mosquée. Les dernières fouilles avant l'Indépendance de l'Algérie ont été menées par Lucien Golvin de 1951 à 1956 puis de 1960 à 1962. À partir de 1964 Rachid Bourouiba a ensuite dirigé chaque année de nouvelles campagnes. On peut ainsi se faire aujourd'hui une idée plus exacte des monuments de la Kalâa que de ceux d'Achir.
La ville comprenait, à l'intérieur d'une fortification de 7 kilomètres, d'une largeur variant entre 1,20 m et 1,60 m, détruite par la suite par les Almohades, une quantité importante de monuments, parmi lesquels une grande mosquée (fondée au XI siècle) et son minaret, ainsi que le donjon du Manar, le palais du Manar, le palais du Lac, le palais du Salut, des citernes et bassins. Trois portes, Bab al-Aqwas, Bab Djenan et Bab Djerawa, donnaient accès à la ville, dont seules les deux premières subsistent. Deux monuments émergent encore du sol: le minaret de la mosquée dont on devine assez bien le décor et le donjon du Manar qui domine la falaise de l'oued Fredj.
