«Колония Юлия Цирта» просуществовала более ста лет. При императоре Веспасиане (69–79 гг. и. э.) ею управлял консул Квинт Аврелий Пактумий Клемент, который правил до 100 г. н. э. Позднее правителем Цирты стал Фронтон, который впоследствии был учителем юного императора Марка Аврелия (161–180 гг.). В этот период Цирта стала столицей огромного региона Нумидии Циртинской. Ее власть распространилась на территории от Гиппона-Диаррита (Бизерты) на востоке до Мавретании на западе, от Средиземного моря на севере до Сахары на юге. В Нумидии было немало значительных для своего времени городов: Тамугади (Тимгад), Ламбесис, Куикуль (Джамиля) и другие.
В середине III в. в Цирте, как и везде в Римской империи, начало укрепляться христианство. Однако при императоре Диоклетиане (284–305 гг.) начались преследования христианских общин. С этим были связаны многочисленные казни христиан в Цирте. Сохранились документы о массовых расправах с руководителями христианских общин в Цирте, произведенных 3 мая 303 г. В память об этих событиях при входе в каньон Рюмеля на правобережных отвесных утесах потом были сделаны латинские древние надписи, а утесы получили название Утесов Мучеников. В 311 г. во время междоусобной войны между императором Константином и Максенцием (правителем Италии) город был до основания разрушен римлянами и восстановлен в 312–315 гг. Константином, переименовавшим Цирту в Константину. В середине V в. Константина была завоевана вандалами, в начале VI в. — византийцами. После прихода арабских войск в Магриб и особенно после завоевания арабами Испании в VIII в. судьба Константины и всей Нумидии была решена — она была завоевана, хотя и продолжала сохранять автономию в управлении. В течение всего VIII в. Нумидия все более подчинялась арабским военачальникам. Особенно усилился этот процесс после отложения Магриба от государства Фатимидов в Египте. На высокие равнины Константины вступило тогда воинственное племя бани-хиллали. Это произошло в 1050 г. В XIII–XV вв. Константина подпала под зависимость от династии Хафсидов. Это было временем процветания города. Ослабление государства Хафсидов в конце XV в. было фатальным для Константины. Мятежи развязали междоусобицу в городе, и город был разрушен. Руины римских зданий в течение длительного времени расхищались, используясь как «каменоломни» для постройки жилищ и культовых зданий.
Крах римской культуры в Северной Африке, смена власти вандалов, византийцев, различных арабских династий обусловили известную автономию в развитии Константины, своеобразие ее архитектуры. Памятники мусульманской архитектуры представлены Соборной мечетью, которая была построена в 1730 г. Аббасом-бен-Амуль Джалилем, марокканцем по происхождению, секретарем бея Хуссейна-бу-Ремия. Семь больших нефов перекрыты величественными сводами. Мощные гранитные колонны, несущие на себе перекрытия, привезены были сюда из римских руин. Большой михраб мечети перекрыт сводом восьмиугольной формы.
Не менее замечательна и мечеть Сиди-Лакхедар. Она построена в 1743 г. и по своим размерам превосходит Соборную мечеть. Ее огромный молитвенный зал имеет 15 нефов. Недалеко от нее расположена третья замечательная мечеть — Салах-Бей, названная в честь ее строителя. Салах-Бей был одним из правителей Константины в период турецкого владычества. В XVI в. власть в Магрибе захватили два корсара, братья Барбаросса — Баба-Аруджит и Кхейр-Эд-Дин, греки по происхождению. Они основали свою резиденцию на острове Джерба в Тунисе. Возглавив войну против испанцев и генуэзцев, оккупировавших некоторые порты Магриба, братья Барбаросса захватили всю территорию Туниса и Алжира, а затем объявили себя вассалами турецкого султана. В 1520 г. город Константина перешел под власть Турции. В середине XVI в. город был охвачен борьбой между ставленником Турции Лефгином и вождем местных арабов Абд-Эль-Муменом. Турецкое влияние сказалось и в последующие времена.
Мечеть Салах-Бея, известная под названием Сиди-Эль-Кеттани, была построена в 1776 г. Молитвенный зал ее, подобно залу мечети Сиди-Лакхедар, разделяется на 15 нефов. Центральный из них перекрыт тремя куполами восьмигранной формы. Сейчас, однако, эта мечеть представляет собой только реставрацию бывшей на ее месте мечети, уничтоженной пожаром.
Памятники гражданской мусульманской архитектуры представлены дворцом последнего бея Константины Эль-Хаджи-Ахмеда. Он был внуком Ахмеда-Эль-Колли, который правил городом в 1759–1771 гг.