En la época de la reconquista a los árabes, Madrigal de las Altas Torres fue arrasada por completo y reconstruida a continuación con el aspecto que ha conservado en parte hasta nuestros días. Su emplazamiento en una llanura abierta a los cuatro vientos hizo aconsejable la edificación de un buen recinto fortificado que la defendiera por todos sus flancos de una nueva destrucción. Así surgieron en el siglo XIII las murallas de estilo mudéjar, que dibujan un círculo perfecto y que dieron nombre a la población, debido a sus “altas torres”. De estas torres subsisten en la actualidad unas veinte, cuatro de ellas sobre las puertas que dan acceso a la villa. Dentro del recinto amurallado se proyecta hacia el cielo, más que ningún otro torreón, el campanario de la iglesia románico-mudéjar de San Nicolás, que alcanza más de 60 m de altura y que también debió de aportar su granito de arena al nombre del lugar. En esta iglesia, que alberga bellos sepulcros con esculturas yacentes, se conserva la pila bautismal en la que se dice que recibió el bautismo Isabel la Católica.
La reina de Castilla nació en Madrigal de las Altas Torres en 1451, cuatro años después de que sus padres, Juan II de Castilla e Isabel de Portugal, contrajeran matrimonio en el palacio real de la población. Lo que queda de este edificio del siglo XV, que es un buen ejemplo de palacio real castellano, forma parte en la actualidad del monasterio de Nuestra Señora de Gracia, regentado por las madres agustinas. A estas monjas lo donó el rey Carlos I en 1527 para que construyeran la iglesia aneja y ellas lo han conservado y lo enseñan a los visitantes.
Más tarde se instalaron en la villa los monjes del convento de San Agustín, que en una placa de su patio herreriano guardan la memoria de fray Luis de León, el ilustre poeta español que tradujo el Cantar de los Cantares y fue catedrático de la Universidad de Salamanca. Fray Luis pasó sus últimos días y murió en el antiguo convento de los agustinos, situado en las proximidades de Madrigal y del que sólo quedan unas pocas ruinas.
El hermoso recinto con soportales de la plaza Mayor también tiene memoria histórica, ya que allí fue ajusticiado públicamente el llamado “pastelero de Madrigal”, un impostor que se hizo pasar por el rey Sebastián de Portugal. Los vecinos que se toman hoy unas tapas de chorizo y de queso bajo los soportales no dan la impresión de recordar que la cabeza del reo quedó expuesta sobre un palo durante varios días. El chorizo es una especialidad de la villa, en particular los chorizos de olla, que son de degustación obligada en la Fiesta de san Nicolás de Bari.