Durante la etapa celtibérica, Gormaz, junto con Uxama, desempeñaban un papel importante en las guerras con Roma debido a su situación en el paso hacia territorios vacceos. Tras un periodo de tiempo entre el final del Imperio y la llegada de los musulmanes, la zona cobra una importancia estratégica de primer orden, siendo Gormaz la plaza preeminente, por ser bastión defensivo de los musulmanes en la frontera del Duero.
La primera ocupación del cerro de Gormaz se debe a pequeños grupos ganaderos de la Edad del Bronce. Algunos restos romanos y visigodos nos señalan la continuidad del poblamiento, pero es con la llegada de los musulmanes cuando el cerro de Gormaz cobra el carácter de fortaleza que hoy refleja.
En el siglo IX los musulmanes construyeron un pequeño castillo en el lado noroeste del cerro, uno de los primeros asentamientos en la provincia. El acoso de los reinos cristianos al norte del Duero ocupando importantes plazas, provoca el reforzamiento de las fronteras, con la construcción del castillo que hoy conocemos.
Fue mandada edificar por Al-Haquem II a finales del siglo X como centro militar de apoyo a Medinaceli, capital entonces de la Frontera Media musulmana. Por sus excelentes condiciones de visibilidad y su situación estratégica, controlando una de las rutas de acceso hacia el norte, su posesión se hacía indispensable para mantener las importantes plazas de esta zona, siendo tomada por ambos bandos en multitud de ocasiones hasta su posesión definitiva por Fernando I en el año 1059. Con los Reyes católicos (siglo XV), pierde su carácter militar y pasa a ser utilizada como cárcel.
Las murallas del castillo, reforzadas por 28 torres, se adaptan a la forma alargada de la meseta sobre la que se asientan con su perímetro de casi un kilómetro, constituyendo ya en su época la fortaleza más grande de Europa. Su carácter eminentemente militar queda patente en la solidez de su fabrica y la austeridad de su decoración. Unas ménsulas de modillones de rollos de tipo califal y tres estelas embutidas en el muro oeste, junto con el arco califal de la puerta son las únicas licencias decorativas que se permitieron sus constructores.
Destacan en el castillo los depósitos de agua, existiendo aljibes en el alcázar y una gran alberca frente a la puerta principal, simbolizando quien es el señor del agua. En uno de los muros de la zona sur cercana a una de las puertas, se localizan tres nichos que pudieron corresponder al mihrab de una mezquita ú oratorio musulmán.