Eremenko on sündinud tegelikult just Moskvas. Soome kolis Vene perest pärit keskväljamees elama 3-aastasena, kui tema isa Aleksei Eremenko, kes mänginud nii Moskva Spartakis kui Moskva Dünamos, siirdus karjääri lõpetama Jarosse.

27-aastane Eremenko on mänginud varasemalt Udineses, Sienas, Moskva Dünamos, Kiievi Dünamos ning Kaasani Rubiinis. Viimati nimetatud klubis oli tema meeskonnakaaslaseks muide ka vanem vend, samuti Soome koondisse kuuluv Aleksei Eremenko Jr.