The work was started in 1090 by Raymond of Burgundy. Most of the walls appear to have been rebuilt in the 12th century. The enclosed area is a rectangle of with a perimeter of some , including 90 semicircular crenellated towers. The walls have an average width of . They have an average height of . The wall has nine fortified gates. The Puerta de San Vicente (Gate of St Vincent) and Puerta del Alcazar (Gate of the Fortress) are flanked by twin towers, high, linked by a semicircular arch. The apse of the cathedral also forms one of the towers. The fortifications are the most complete in Spain.