К числу очень важных событий из времени Феодосия II надо, безусловно, отнести сооружение константинопольских стен. Уже Константин Великий окружил новую столицу стеной с суши и с моря. Но ко времени Феодосия II город разросся далеко за пределы сухопутной стены Константина. Необходимо было принять новые меры к защите города от нападения врагов. Пример Рима, взятого в 410 году Аларихом, служил серьезным предостережением для Константинополя, которому в первой половине V века угрожали гунны.

Для выполнения столь трудной задачи нашлись около Феодосия талантливые и энергичные люди. Стены строились при нем в два приема. Еще в малолетство Феодосия в 413 году регент префект претория Анфимий соорудил сухопутную стену с многочисленными башнями, от Мраморного моря до Золотого Рога, в некотором расстоянии на запад от стены Константина. Стена Анфимия, спасшая столицу от нападения Аттилы, существует и по настоящее время, на расстоянии от Мраморного моря на север до развалин византийского дворца, известного под названием Текфур-сарая. После сильного землетрясения, повредившего стены, префекты Кир и Константин, которых в науке нередко отождествляют, уже в конце царствования Феодосия не только исправили стену Анфимия, но и соорудили впереди нее еще стену, также со многими башнями, перед которой вырыли глубокий и широкий, наполненный водой ров. Таким образом, с суши получился тройной ряд укреплений, уцелевших до нашего времени: две стены и перед ними ров. При Кире были также построены стены вдоль берега моря. С его именем также связывается введение ночного уличного освещения в столице. Сохранившиеся от того времени до наших дней на стенах две надписи, одна греческая, другая латинская, говорят о строительной деятельности Феодосия.