Según documento fechado el 12 de octubre de 1456, don Juan Pacheco, primer Marqués de Villena, ordenó construir una fortaleza o castillo, concebido como palacio y fortaleza, de estilo gótico-mudéjar, en lo alto del cerro de San Cristóbal y una muralla o cerca de cal y canto que rodease la Villa hasta el castillo, cuya tercera parte sería costeada por el marqués y el resto por sus vasallos, los vecinos de Belmonte (“sea cercada e rodeada en derredor con una cerca de cal e canto”).

Su arquitecto fue seguramente Juan Guas, cuyo trabajo para el marqués está documentado en otras obras, como el Monasterio de El Parral en Segovia, si bien la época en que está construido y la existencia de elementos decorativos exactamente igual que los de La Colegiata, así como las marcas de canteros, exactamente iguales también en ambas construcciones, hacen también pensar en el maestro cantero Hanequín de Bruselas.