Wyznaczył na następny rok na konsulów pogan, a 2 września podpisał ustawę zakazującą mnichom pobytu w miastach. W końcu jednak zaakceptował warunki Ambrożego i po pokucie został z powrotem przyjęty do grona wiernych. Stało się to w Boże Narodzenie 390 roku.
Wojna z Eugeniuszem Kiedy po śmierci Walentyniana II w 392 roku frankijski wódz Arbogast wyniósł do roli pretendenta eksnauczyciela retoryki, zwolennika pogan Eugeniusza, Teodozjusz jeszcze zaostrzył zakazy kultu jakichkolwiek bogów, składania ofiar przed podobiznami bogów, zapalania im świateł, palenia kadzideł, zawieszania wieńców. Uznał badanie wnętrzności zwierząt ofiarnych za zbrodnię obrazy majestatu. Nakazał wszystkie pogańskie miejsca kultu zająć skarbowi państwa. Każde wykroczenie przeciw tym zarządzeniom miało podlegać surowym karom: sędziów, naczelników miast i członków rad miejskich wezwano do wykonania dekretu. Gdy na Wschodzie opublikowano edykt cesarski, senatorowie rzymscy, zachęceni przez Eugeniusza, uroczyście wznowili pogańskie ceremonie. Wtedy Teodozjusz zdecydował się podjąć wyprawę zbrojną przeciwko Arbogastowi i Eugeniuszowi. W 394 roku wyruszył z armią wschodnią w pole przeciw Eugeniuszowi, który obsadził przełęcze Alp Julijskich. W bitwie nad rzeką Frigidus Teodozjusz odniósł zwycięstwo dzięki temu, że nagle z północy nadciągnęła burza.