Prychynenko debuteerde op 31 maart 2012 voor Hearts FC in de thuiswedstrijd tegen Aberdeen FC. De wedstrijd werd met 3-0 gewonnen.
Hij speelde 5 seizoenen als publiekslieveling bij Beerschot en bracht Beerschot mee terug naar Eerste klasse A. Na de finalewedstrijd in 1B tussen Beerschot en OH Leuven ging hij de geschiedenisboeken in met zijn legendarische uitspraak: "F*ck the haters, we are legends now!".
Zijn vader Sergei, voorheen voetballer bij onder meer CSKA Moskou en Lokomotiv Moskou, is Oekraïens. Moeder Elena komt uit Wit-Rusland. Prychynenko voelt zich echter Duitser. Op drie jaar na heeft hij ook zijn hele jeugd in Duitsland gewoond.
Daarom veranderde Prychynenko zijn nationaliteit op zijn 18e van Oekraïens naar Duits, ook om te garanderen dat hij zonder werkvergunning kon spelen voor Hearts FC.