The double Theodosian Walls located about 2 km to the west of the old Constantinian Wall, were erected during the reign of Emperor Theodosius II (408–450), after whom they were named. The work was carried out in two phases, with the first phase erected during Theodosius' minority under the direction of Anthemius, thepraetorian prefect of the East, and was finished in 413 according to a law in the Codex Theodosianus. An inscription discovered in 1993 however records that the work lasted for nine years, indicating that construction had already begun ca. 404/405, in the reign of Emperor Arcadius (395–408). This initial construction consisted of a single curtain wall with towers, which now forms the inner circuit of the Theodosian Walls.

Both the Constantinian and the original Theodosian walls were severely damaged, however, in two earthquakes, on 25 September 437 and on 6 November 447. The latter was especially powerful, and destroyed large parts of the wall, including 57 towers. Subsequent earthquakes, including another major one in January 448, compounded the damage. Theodosius II ordered the praetorian prefect Constantine to supervise the repairs, made all the more urgent as the city was threatened by the presence of Attila the Hun in the Balkans. Employing the city's "Circus factions" in the work, the walls were restored in a record 60 days, according to the Byzantine chroniclers and three inscriptions found in situ. It is at this date that the majority of scholars believe the second, outer wall to have been added, as well as a wide moat opened in front of the walls, but the validity of this interpretation is questionable; the outer wall was possibly an integral part of the original fortification concept.

Throughout their history, the walls were damaged by earthquakes and floods of the Lycus river. Repairs were undertaken on numerous occasions, as testified by the numerous inscriptions commemorating the emperors or their servants who undertook to restore them. The responsibility for these repairs rested on an official variously known as the Domestic of the Walls or the Count of the Walls, who employed the services of the city's populace in this task After the Latin conquest of 1204, the walls fell increasingly into disrepair, and the revived post-1261 Byzantine state lacked the resources to maintain them, except in times of direct threat.