V [[7. storočie|7. storočí]] mesto prakticky zničili prichádzajúci [[Arabi]]. Za [[Abbásovci|Abbásovcov]] sa stalo súčasťou provincie emirátu Ifrikíja, v ktorej vládli Aghlabidi, a neskôr [[kalifát]]u [[FatimovciFátimovci|FatimovcovFátimovcov]]. Za nich mesto získalo v 10. storočí obmedzenú samostatnosť a jeho význam pre obchod tým vzrástol. V [[11. storočie|11. storočí]] sa dostalo do správy emirov z Bedžaja a od [[13. storočie|13. storočia]] bolo pod správou [[Tunis]]u, v ktorom vládla dynastia Hafsidov. Mesto malo v tej dobe obchodné styky s [[Janovská republika|Janovom]], [[Pisa|Pisou]] a [[Benátky (mesto)|Benátkami]]. V r. [[1568]] sa Constantine dostala do područia [[Osmanská ríša|Osmanskej ríše]], ktorí sem umiestnili sídlo beja. Posledným bejom bol Ahmed Bej, ktorý bol vymenovaný alžírskym [[Paša|pašom]] a ktorý viedol boj proti francúzskej koloniálnej expanzii.
