Kariera zawodowa Po powrocie z Holandii pracował w teatrze dziecięcym „Zazerkalie”, gdzie poznał swoją przyszłą żonę, Mariannę, a także wokalistę Dienisa Klawiera. W 1994 założył z nim zespół Czaj Wdwojom, pod którego szyldem wydali dziesięć albumów studyjnych: Ja nie zabudu... (1997), Poputczica (1998), Radi tiebia (1999), Nierodnaja (2000), Laskowaja moja... (2002), 10 tysiach slow o lubwi (2005), Wieczernieje czajepitije (2005), Utrennieje czajepitije (2005), Prosti... (2006) i Biełoje płatje. W 2007 wzięli udział w programie Cirk zo zwiozdami, będącym rosyjską wersją formatu Celebrity Circus, w Polsce znanym jako Gwiezdny cyrk. W 2012 zakończyli współpracę. Niedługo później Kostiuszkin założył nowy zespół – Stanley Shulman Band, który został nazwany na cześć dziadka piosenkarza, Józefa Szulmana. thumb|Kostiuszkin (2013) W 2012 rozpoczął projekt muzyczny o nazwie A-Dessa. Wydał wówczas dwa single: „Fire” i „Sirien”, który został nagrany w towarzystwie zespołu NieAngieły. Jesienią 2014 wydał singiel „Żenszcziny, ja nie tancuju!”.
Uczestniczył w telewizyjnych programach rozrywkowych: Tancy so zwiozdami (2013) i Tocz-w-tocz (2015). Prowadził program Oczen karaoczen (2016) w Muz-TV.