İlk taht naibi, Doğu'nun [[Praetorianpraefectus Prefectpraetorio]]'isu olan [[Anthemius (praetorianpraefectus prefectpraetorio)|Anthemius]] olmuştur. Anthemius'un naipliği zamanından geriye kalan en önemli eser, adına ''Theodosius surları'' denen Konstantinopolis şehir surları olmuştur. Bu şehir surları şimdi görülen üç sıra duvardan oluşmamakta ve sadece tek bir sıra duvar olarak 413 yılında Theodosius daha 12 yaşında iken yapılmasına başlanmıştı. Anthemius bunlar yanında İran [[Sasaniler]]i ile yeni bir barış anlaşması yapılmasına, Hun Kralı Uldin'in başarısız kalan bir istila niyetli hücumundan sonra Bizans Tuna donanmasının takviye edilmesine, [[İskenderiye]]'den Konstantinopolis'e zahire tedarik sisteminin daha geliştirilmesine ve Arcadius'un ölümünden sonra Batı Roma İmparatorluğu ile iyi ilişkiler kurulmasına da neden olmuştur. Anthemius, 413 yılında bu görevden atılmasına kadar gerçek imparator gibi iktidar gücünü hiçbir sınır olmaksızın kullanmıştır.
