Keino was born in Kipsamo, Nandi District, Kenya. Both of his parents died while he was young. He was then brought up by his aunt. After finishing school, he joined the Kenya Police. Before taking up athletics, he played rugby.
He began his international career at the 1962 Commonwealth Games in Perth, Australia where he came eleventh in the three miles. At the 1964 Summer Olympics he finished fifth in 5000 m and barely missed the 1500 m final.
On 27 August 1965, Keino lowered the 3000 m world record by over 6 seconds to 7:39.6 at his first attempt at the distance. He won two gold medals (1500 & 5000 metres) at the inaugural All-Africa Games. Later in that year he broke the 5000 m world record held by Ron Clarke clocking 13:24.2. At the 1966 Commonwealth Games in Kingston, Jamaica he won both the mile run and three mile run. In the next Commonwealth Games, Keino won the 1500 metres and was third in the 5000 metres.