Koelkov leverde zijn beste prestatie in 2008 met het winnen van de marathon van Zürich. Later dat jaar maakte hij zijn olympisch debuut op de Olympische Spelen van Peking. Hij nam deel aan de olympische marathon en finishte als 29e in 2:18.11. De wedstrijd werd gewonnen door de EthiopiërSamuel Wanjiru in een nieuw olympisch record van 2:06.32. In 2009 nam hij opnieuw deel aan de marathon van Zürich, maar kon ondanks een persoonlijk record van 2:10.13 de wedstrijd niet winnen. Hij finishte als tweede met slechts drie seconden achterstand op de EritreërTadesse Abraham.