Sebastiano estaba casado con la hija de Bonifacio, quién era comes Africae, y su esposa Pelagia. Su suegro fue nombrado magister militum en el año 432 por la regente Gala Placidia en sustitución de Flavio Aecio.^[3]​ Este aceptó, inicialmente, la pérdida de su cargo pero, el intento de acabar con él, llevó a una breve guerra civil, durante la que fue derrotado en la batalla de Rímini ese mismo año 432. A pesar de su victoria, Bonifacio murió por las heridas.^[3]​

Sebastiano fue elevado al cargo de magister militum en sustitución de su suegro.^[3]​ Aecio, por su parte, huyó al territorio de los hunos donde consiguió formar un ejército para volver con él a Italia y recuperar su posición al mando del ejército romano.^[3]​ La corte de Rávena, ante su demostración de fuerza, lo volvió a restituir en su puesto y destituyó a Sebastiano.^[3]​

Tras perder el cargo, Sebastiano huyó a Constantinopla con varios de sus seguidores. Estos formaron un grupo dedicado a la piratería en los Dardanelos, actividad que fue cubierta por Sebastiano con la colaboración de varios eunucos del palacio.^[2]​ Su situación se fue volviendo insostenible con el tiempo y en el año 440 tuvo que abandonar el Imperio oriental.^[2]​

Recabó, primeramente, en la corte del rey visigodo Teodorico I tras lo que se trasladó a Barcelona cuando la corte de Rávena lo declaró enemigo público.^[2]​ Allí fue localizado y perseguido por lo que continuó su huida hasta llegar al reino vándalo en África. Genserico lo recibió bien y le asignó un puesto de consejero.^[2]​ Con el tiempo comenzó a desconfiar de sus actividades y le hizo ejecutar en el año 450.^[2]​