Nació en Escitia Menor dentro de una de las más importantes familias de esta provincia romana. Se trasladó a Constantinopla donde comenzó su carrera dentro de los protectores domesticus algo que le permitió entrar en contacto con las principales personalidades del gobierno imperial y cultivar unas relaciones que facilitarían su carrera posterior. Contrajo matrimonio con una noble italiana adinerada del que nacería Flavio Aecio sobre el año 390.
Formó parte de la expedición organizada por Teodosio para acabar con la usurpación de Eugenio y que consiguió derrotarlo decisivamente en la batalla del Frígido en septiembre de 394. Tras la victoria, Teodosio reunificó ambas mitades del Imperio en su persona durante unos meses hasta su muerte en enero de 395 en Milán. Gaudencio no retornó a Constantinopla sino que permaneció en la península italiana donde entró al servicio de Honorio, el nuevo emperador occidental.
Fue nombrado comes Africae y se trasladó a la provincia de África en el año 399 donde, junto a Jovio, se ocupó de restablecer la administración imperial tras la derrota del usurpador Gildo en el año anterior.
Después de su servicio en África fue destinado a la Galia en el año 400 y se le nombró magister equitum per Gallias. Allí se hizo cargo de las tropas comitatenses hasta el año 407 cuando fue asesinado durante un motín de sus soldados. Le sucedió en el cargo Sarus, enviado por Estilicón al frente de una expedición cuyo objetivo era acabar con el usurpador Constantino de Britania.
No está clara la fecha de su muerte que se produjo con anterioridad al año 425. Debido a la falta de fuentes, se barajan dos posibilidades: bien falleció entre los años 423 y 425 dentro del contexto de la usurpación de Juan; o más bien, en el año 407 cuando, tras la invasión de la Galia por un conglomerado de tribus bárbaras, Constantino de Britania desembarcó en la Galia y las tropas estacionadas allí se pasaron en masa a su bando. Esta última opción parece ser la más probable por su encaje lógico con los sucesos acaecidos durante esta invasión y por lo anormal de no tener noticias sobre Gaudencio durante un plazo de tiempo tan extenso como los 17 años transcurridos entre el 407 y el 424.
Imperio romano de Occidente