They were built as an extension of the original 9th-century Muslim Walls of Madrid to accommodate the new districts which emerged after the Reconquista (11th–13th centuries).
Some of the remains are still standing, however, and are integrated into the structure of various buildings in El Madrid de los Austrias, a name designating the Habsburgs' historic center of the city.
Tradition attributes the construction of the walls to King Alfonso VII of León and Castile (1126–1157), although it is likely that work began before his reign, in the years immediately following the Christian conquest of Madrid (1083).
The properties of flint (which, when struck, causes sparks) gave rise to one of the historic city slogans: "I was on water built, my walls are of fire."
The Tower de los Huesos, built in the 11th century during the Muslim occupation of the city, was incorporated into the Christian Walls to protect the Valnadú Gate.