Руфина и без того ненавидели, поскольку он из жадности и природной жестокости беззастенчиво злоупотреблял своим положением: под любым предлогом конфисковывал имения, торговал должностями, выносил крайне суровые приговоры. С другой стороны, Руфин стремился обеспечить себе поддержку духовенства, яростно преследуя язычников и еретиков и одновременно закладывая монастыри и строя часовни.
При дворе подозревали, что Руфин лелеет чрезвычайно честолюбивые помыслы и жаждет выдать свою дочь за Аркадия. Однако его злейший враг, евнух Евтропий, сумел нанести упреждающий удар, женив Аркадия на красавице Евдоксии. Евдоксия была дочерью умершего за несколько лет до этого полководца по имени Бауто, франка по происхождению. После смерти отца она воспитывалась в доме непримиримого врага Руфина, Промота (он погиб в 391 году в бою с готами, попав в засаду, устроенную, как поговаривали, не без ведома самого Руфина). Брак был заключен в спешке, вызванной стремлением избежать возможного противодействия со стороны могущественного префекта. Поэтому свадебная церемония состоялась уже 27 апреля 395 года, спустя всего три месяца после смерти Феодосия, еще до окончания траура, а собственно, даже до похорон — тело покойного было доставлено в Константинополь из Медиолана лишь в ноябре того же года и восьмого числа того же месяца захоронено в соборе Святых Апостолов.
Красавица Евдоксия, как позже выяснилось, обладала отнюдь не прекрасными чертами характера. Она была жадна, мелочна, фанатично религиозна и находилась под влиянием духовенства, но в то же самое время способна была жестоко расправляться с вызывавшими ее недовольство священнослужителями. Но пока юная и неопытная императрица еще не занималась интригами, так что Руфин мог чувствовать себя в безопасности, хотя Евдоксия очень быстро приобрела огромное влияние на мужа.
Удар обрушился на префекта с совершенно иной стороны, причем абсолютно неожиданно. Осенью Аркадий — разумеется, с ведома Руфина, а скорее всего по его совету, — потребовал от Стилихона, чтобы он вернулся в Италию, поскольку никаких успехов в его борьбе с вестготами не наблюдалось. Император также приказал полководцу вернуть обратно те воинские части, которые входили в состав восточной армии и были взяты Феодосием в поход на запад. Стилихон подчинился воле правителя, сам отправился на запад, а в Константинополь отослал соответствующие воинские соединения под командованием Гайны. Гайна был готом по происхождению, он многие годы прослужил в римской армии и отличился в походе против Евгения.
27 ноября Гайна командовал войсками, возвратившимися в Константинополь и расположившимися в пригороде Эвдом. Император вместе с Руфином отправился туда приветствовать вернувшихся воинов. Но в какой-то момент торжественная церемония обернулась трагедией: по приказу Гайны солдаты окружили Руфина и убили его прямо на глазах у стоявшего рядом Аркадия. Все современники в один голос утверждали, что это было сделано в соответствии с тайным приказом, полученным Гайной от Стилихона.
Император, чье величество оказалось в буквальном смысле испачкано кровью его ближайшего советника, высокопоставленного сановника, мог лишь сделать вид, что все произошедшее свершилось с его ведома и согласия. Поэтому он тут же конфисковал все имения Руфина, однако не вернул их тем, у кого они были отобраны префектом, а подарил своему новому любимцу и всевластному советнику Евтропию.
С этого момента началось правление Евтропия, которое от предыдущего отличалось, пожалуй, лишь тем, что суды реже выносили виновным (или оклеветанным) смертные приговоры, зато чаще отправляли в ссылку, тогда как имущество у подсудимых отбирали точно так же, как и раньше — для удовлетворения ненасытной жадности евнуха и его приспешников.
В то же самое время усиливалось и влияние Евдоксии. Ее вечно сонный супруг, ленивый и неповоротливый в делах государственных, проявил завидное трудолюбие на ином поле деятельности. Уже в 397 году императрица родила своего первого ребенка — девочку, которая вскоре умерла. Через два года родилась еще одна девочка, которую назвали Пульхерией, еще через год — третья дочь, Аркадия, и, наконец, в 401 году на свет появился сын — ему дали имя деда, Феодосий. Последним ребенком, родившимся в 403 году, была еще одна девочка, Марина.
Ситуация в борьбе с захватчиками все еще оставалась сложной. Аларих снова вторгся в Грецию в 396 году, а потом и в следующем, а помощь Стилихона снова оказалась безрезультатной. Добиться удалось лишь того, что готы отступили на земли Эпира. Однако чуть позже Евтропию удалось найти удачное решение, которое помогло справиться с этой напастью — Алариха назначили командующим римскими войсками в Иллирии! Таким образом, вчерашний враг вдруг стал офицером самого высокого ранга, ответственным за спокойствие провинции и нерушимость границ. И, кроме того, он становился как бы стеной, разделявшей две части империи — а в сущности, два государства.
