Os romanos iniciaram o povoamento da região, fundando a cidade de Bílbilis ou Augusta Bílbilis (em latim: Augusta Bilbilis) a aproximadamente quatro quilômetros ao norte da atual Catalayud. A cidade moderna foi fundada pelos mouros em torno do castelo de onde provém o seu nome com o nome "Alcalá Aiube" (em árabe: القلعة أيوب; romaniz.:Al-qal'a 'Ayyūb; lit. "O Castelo de Aiube"). A cidade foi conquistada por Afonso I de Aragão em 1120. Foi capital de sua própria província durante três anos, no século XIX.