He was granted the title of "comes rei militaris per Britanniarum" (Commander of the Troops of the Diocese of the Britains) by the emperor Valentinian for his work there; putting down the Great Conspiracy (367–368) and the usurpation of Valentinus. After restoring order in Britain he returned to continental Europe and fought against the Alemanni; as Valentinian's "magister equitum" (Master of Horse) he successfully invaded Alemannic territory (371 or 370). In 372 Theodosius led a successful campaign against the Sarmatians. In the same year Firmus, a Mauritanian prince, rebelled against Roman rule. Theodosius was sent to Africa and in two hard-fought campaigns (373–374) put down the insurrection. In 376, after the death of emperor Valentinian, he was arrested and executed, presumably as he was seen as a threat to the new western emperors Gratian and Valentinian II.