Kelai won the 2003 Singapore Marathon, the 2004 Brussels Marathon, and was the 2007 winner of the Toronto Waterfront Marathon. In 2009 he was third at the Mumbai Marathon, failing to defend his title, and took fourth at both the Singapore and Karstadt Marathons.
He was selected for the marathon at the 2010 Commonwealth Games and he moved away from the field in the final 10 km to become Commonwealth champion (only the second Kenyan man to take the title after Douglas Wakiihuri). "I am so humbled to win here. It is an honour. I didn't know I could be the winner", said Kelai, "I feel on top of the world". He stayed on in Asia for 2011, coming sixth at the Mumbai Marathon and third in Singapore.