Оба сына Феодосия, когда унаследовали трон, были еще совсем в юном возрасте: Аркадию было 17 или 18, Гонорию — только 10 лет. Повзрослев, оба проявили характер слабый и ленивый. В результате правление империей велось от их имени другими лицами. На Западе в течение 13 лет реальным правителем был вандал полководец Стилихон, который в последние месяцы правления Феодосия был верховным командующим большей части имперской армии — как ее восточных сил, которые подавили Евгения, так и потерпевшей поражение армии Запада. Он женился на Серене, племяннице Феодосия и, умирая, Феодосий назначил его опекуном обоих своих сыновей. На Западе Стилихон укрепил свои позиции, сосредоточив в своих руках командование армией. Он занимал посты magister peditum и magister equitum praesentalis, получившие объединенное название magister utriusque militae, a все другие magistri были de facto (фактически), если не de iure (юридически) подчинены его власти. Все comités rei militares и duces находились в его распоряжении и главные служащие всех ведомств назначались из служащих praesentales.
Тем не менее на Востоке генерал Стилихон натолкнулся на решительное сопротивление. Здесь верховная власть сначала принадлежала преторианскому префекту Руфину, барристеру из Аквитании, который пользовался большим расположением Феодосия. Напряженными отношениями между западной и восточной частями империи воспользовался Аларих, недавно избранный король вестготов северной Фракии, который двинулся на юг и опустошил окрестности Константинополя. Руфин заставил его повернуть на запад, в сторону Греции, а Стилихон выслал большую армию для борьбы с ним. Это стало причиной разногласий между Стилихоном и Руфином. Руфин требовал возвращения восточных войск, подавивших Евгения, и требовал сделать Иллирию (провинции Дакию и Македонию) частью Восточной империи. Стилихон согласился с обоими требованиями, но подстроил так, что Гайнас, готский офицер возвращавшейся восточной армии, убил Руфина.
Но Стилихон, надеявшийся таким образом сохранить контроль над Востоком, был разочарован. Человеком, пришедшим на смену Руфину, был Евтропий, старший евнух Аркадия, и он занял по отношению к Стилихону такую же враждебную позицию, как в свое время Руфин. Когда в 397 году Стилихон послал морем войска для того, чтобы окружить Алариха в Греции, ему вновь было приказано прекратить эту акцию, а Аларих был назначен Евтропием magister militum Иллирии. Он также всячески помогал и оказывал моральную поддержку Гильдону, magister militum в Африке, когда тот поднял восстание в 397 году. Но Стилихон вскоре заставил Африку еще раз подчиниться своей воле.
В 399 году Гайна, magistri militum praesentales на Востоке, стал во главе группы восставших остготских laeti и потребовал казни Евтропия. Евтропий был разжалован и убит, но Гайне не удалось стать правителем Востока. Большое количество готов, которых он привел с собой в Константинополь, было перерезано городскими жителями, а бразды правления захватил Аврелиан, который был назначен преторианским префектом. Аврелиан был сыном Тавра, человека незнатного происхождения, занимавшего должность преторианского префекта и консула при Констанции II. Он был известен как лидер образовавшейся среди аристократов партии, которая хотела сместить германцев с высших командных постов в армии. На какое-то время он назначил magister militum Фравитгу, еще одного гота, разбившего Гайну и выгнавшего его из империи. Через короткое время Фравитга был разжалован и в течение последующих нескольких лет генералами были только римляне. Контроль над восточными частями находился в руках преторианских префектов, Аврелиана и сменившего его в 405 году Анфемия, внука Филиппа, сына колбасника, который служил консулом при Констанции II.