Toda la muela estuvo rodeada de una muralla que protegía la población, despoblada y expoliada desde los años setenta, y perteneciente a las Villas Fronteras con Aragón, del arciprestazgo de Gómara. Conocida como Alcaçar desde el fuero de Soria del siglo XIII, y posteriormente como Peña de Alcázar, denota claramente su origen árabe (Al-qasr, fortaleza).

Antonio Ubieto, en el último tercio de este siglo, ubica en Peñalcázar el Alcocer del Cantar del Mýo Çid, a cuya toma dedica el poema no pocas líneas, aunque Guillermo García propone una localización mucho más lógica con el texto y el terreno entre Ateca y Terrer.

Su importancia en la Edad Media queda atestiguada por las ruinas que hoy se conservan y los objetos y sepulcros encontrados. Según fuentes de la AEAC en la obra "Corpus de castillos medievales de Castilla", contaba con dos entradas con dos formidables puertas de hierro, hoy devastadas. Hay testimonios de poblaciones íberas y dos cavernas pobladas en la prehistoria, la de las Brujas y la del Viñador.

Del alcázar hoy sólo queda un centenar aproximado de metros del lienzo de la muralla por su lado Oeste y recintos más o menos aislados, con algunas almenas en aceptable estado para el conjunto. El camino de acceso en rampa pavimentada, zigzaguea hasta alcanzar una de las puertas de acceso, que divide uno de los lienzos. En una de las torres de la muralla también por su lado Oeste, o más bien en sus restos, se aprecia lo que pudo ser un aljibe o nevera. Se trata de una bóveda de cañón insertada en una torre cuya parte superior aparece a ras de suelo con una abertura (¡cuidado al acercarte!).

Es sólo por este lado de la muela, por el collado de la sierra de La Quiñonería, por donde se puede acceder con cierta facilidad, desde las proximidades de la cantera, que deberás rodear por su izquierda, o bien subiendo por una antigua calzada a la derecha de ésta, aunque existe un sendero mucho más empinado por el lado de La Quiñonería, al final de un camino agrícola que sale de la carretera de ésta a Carabantes y La Alameda. Si has pasado antes por Almazul habrás podido ver los restos de una torre que bien pudo ser una avanzada de señales para este alcázar por el valle del Río Peñalcázar.

En un artículo de Ángel Almazán en Revista de Soria (nº9, verano de 1995), podemos leer la descripción que José María Lucas, estudioso y  otro enamorado de Peñalcázar, hace de su patrimonio en las murallas, la iglesia del siglo XVI, un antiguo camino romano, defensas romanas y celtibéricas, restos de una ermita de principios del siglo XVIII (Madoz señala dos ermitas en el término), yacimientos fósiles, dos cuevas y unas pocas construcciones romanas. Lucas, entre otros, sitúa aquí la Centríbriga celtíbero-romana (que traduce como alta fortaleza), sometida poco después de la toma de Numancia.

En el 972, a la muerte de Amril ben-Timlet, el valí del Campo de Gómara y el Jalón medio, sus hijos gobiernan las torres de Amril y Noviercas, y las plazas de Peñalcázar, Ateca, Deza y Ribarroya. No es aventurado suponer que pudo ser tomada por el Conde Garci Fernández en su ataque contra Deza en el 974, y en el que vence a los valíes en el inlocalizado Fahs Albaracat ("el campo de las bendiciones").

En 1358 don Enrique de Trastámara, rompiendo las débiles paces entre aragoneses y castellanos del Cardenal Guillén, trata de hacerse con Peñalcázar, aunque tiene que retirarse de nuevo a Aragón ante el empuje de su hermanastro don Pedro I (El Cruel) desde Gómara.

En 1447 los navarros toman Peñalcázar. Pudo ser la respuesta a la toma de Atienza, que estaba en manos navarras, por parte de Juan II de castilla un año antes.

De 1581 era el retablo mayor de la parroquial de San Miguel en Peñalcázar, elaborado por Juan de Artiaga, del que se han conservado dos imágenes, de la Dolorosa y San Juan. El estofado era obra de Pedro Jiménez de Santiago, de 1596. Según Ángel Almazán una virgen románica del siglo III se encuentra probablemente en el palacio episcopal de El Burgo de Osma.

Durante la Guerra de Sucesión es tomada y saqueada por las tropas del Archiduque en 1706, junto con las villas de Deza, Serón, Almazán y Almenar, retirándose un año después.

Una leyenda, recogida por Florentino Zamora Lucas, cuenta de como Blanca, la hija de Don Nuño, señor del castillo de San Pedro Manrique, fue raptada en la capilla de la Virgen de la Peña por el moro Yacub-Aben-Said y llevada a su guarida en el castillo de Armejún (próximo a San Pedro Manrique). Siendo sitiado el castillo por los hombres de Don Nuño, Yacub arrojó el cuerpo inanimado de Blanca sobre su campo. En esto apareció el Apóstol Santiago de peregrino que, desde un cerro llamado el Portillejo y usando una honda, lanzó una piedrecilla que se fue agrandando y aplastó a los moros. La iglesia parroquial de Peñazcurra, fue levantada en 1573 y dedicada a Santiago como testimonio de este acontecimiento.

Ninguna relación tiene esta leyenda con Peñalcázar de no ser porque Gervasio Manrique de Lara ubica aquí esta otra: El caudillo sarraceno Yucut se enamora de Beatriz, hija del alcaide de San Pedro Manrique, Don Nuño, a la que rapta y lleva a la fortaleza de Peñalcázar. Ante el ataque de Don Nuño, Yucut lanza a Beatriz desde los altos de las montañas, cayendo entre los peñascales de la sierra por donde avanzaba el ejército cristiano. Una paloma la había sostenido entre sus alas y la encontraron sana y salva. En aquel instante se apareció Santiago montando en un caballo, que lanzando una piedra contra los parapetos moriscos resquebraja la montaña, desmoronándose la fortaleza de Peñalcázar y quedando Yucut y los suyos sepultados en una profunda sima. Las similitudes son más que evidentes, pero ¿cuál es la localización correcta?... No importa, son leyendas, sólo disfruta de ellas.

Contaba en 1783, próximo a la disolución del Honrado Concejo de la Mesta, con un total de 6.350 cabezas de ganado lanar, 200 de ellas trashumantes, en un momento en que la provincia contaba con más de 670.000 cabezas.

Tuvo minas de galena argentífera y se extraía plata. A mediados del siglo XIX, según Madoz contaba con setenta casas, ayuntamiento, escuela, parroquial. Ya no queda otra cosa que no sean ruinas; y ese es el destino escrito de tantos otros pueblos de esta provincia.