Jesjtsjenko werd bekend toen hij in 2006 na periodes bij Zvezda Irkoetsk en FK Chimki de overstap maakte naar de Oekraïense topclub Dynamo Kiev. Hij wist er niet door te breken, maar op huurbasis bij Dinamo Moskou, Dnipro en Arsenal Kiev kwam hij alsnog aan zijn speelminuten toe. In 2011 keerde de verdediger terug naar zijn vaderland Rusland, waar hij een contract tekende bij Volga Nizjni Novgorod. In 2012 speelde Jesjtsjenko voor Lokomotiv Moskou en op 12 januari 2013 ondertekende de international een driejarige verbintenis bij Anzji Machatsjkala.[1] Die club verhuurde hem later aan Koeban Krasnodar.[2] Begin 2016 huurde Dinamo Moskou hem voor een halfjaar.[3] Na afloop van deze verhuurperiode stapte Jesjtsjenko transfervrij over naar Spartak Moskou.[4] Aan het einde van het seizoen 2018/19 verlengde de verdediger zijn verbintenis met één seizoen, tot medio 2020.[5] In januari 2022 besloot Jesjtsjenko op zevenendertigjarige leeftijd een punt te zetten achter zijn actieve loopbaan.[6]