Aunque el origen de la ciudad no carece de elementos legendarios, se sabe que la construcción comenzó a finales del 936 de la era cristiana, estando las obras a cargo del maestro alarife Maslama ben Abdallah, y se continuó durante los cuarenta siguientes, alcanzando los tiempos de su hijo y sucesor en el califato, al-Hákam II.