Majoring in the accordion, Shufutinsky graduated from the music college named after Ippolitova-Ivanova with specialization coryphaeus.
He appeared with different bands in Moscow’s and Magadan's restaurants (performing Alexander Vertinsky's and Petr Leschenko’s songs), and later became leader of the instrumental band "Leisia Pesnia", which usually played Viacheslav Dobrynin’s songs.
In 1981 he and his family immigrated to the USA. Over a span of 10 years he had appeared with different bands in different restaurants, and created his own show – band "Ataman-band" (named after the restaurant Ataman). He also goes to Russia with tours regularly. In 1990, he accepted an invitation to visit Russia and sang at 75 packed stadium concerts.
In 1998 he wrote an autobiography called I vot stoiu ia na puti… ("And so, I'm standing on the path…")
His repertoire contains songs by such songwriters as Vyacheslav Dobrynin ("Dve svechi" - "Two candles"), Igor Krutoy ("3 sentiabria" - "The 3 of September"; "Palma de Maiorka" - "The Majorca palm"; "Moskovskoie taksi" - "Moscow taxi"; "Moskva slezam ne verit" - "Moscow doesn’t believe in tears"), Oleg Mityaev ("Nochnoi gost" - "Night guest"), Aleksandr Rozenbaum ("Khreschatik", "Zakhodite k nam na ogoniok", "Visit our place", "Gop-stop"), Oleg Gazmanov, Igor Zubkov, Vatslav Lisovskii, Olesia Atlanova, Karen Kavaleryan, and many others.