Les travaux du château débutèrent parallèlement à ceux de la cathédrale, quoiqu’ils durèrent moins longtemps. La substitution des constructions préexistantes de l’époque d’Al-Andalus eut lieu à la fin du XIIe siècle ou au cours des premières années du XIIIe siècle. C’est à cette période que l’on situe les nefs sud-est et sud-ouest. La première fut destinée au logement et fournissait un lieu de réunion et d’assemblée, et la seconde, couronnée par un ciborium à l’extérieur, servait de chapelle et d’espace de culte.

Cependant, c’est au cours de la deuxième moitié du XIVe siècle que la structure du château fut configurée et les diverses salles entièrement définies. À cette époque vinrent s’ajouter aux nefs déjà construites la nef nord-ouest, destinée à accueillir les chambres royales, et une nouvelle chapelle. La nef nord-est garda son rôle défensif et de stockage.

Le résultat de ce processus est un édifice de plan rectangulaire formé de quatre nefs tout autour d’une cour centrale dotée d’une citerne. L’apport financier de plusieurs rois contribua à sa construction, entre autres Pierre Ier le Catholique, Jacques Ier le Conquérant ou Pierre III le Cérémonieux.