Uchimura iniciou no desporto, aos três anos de idade, em um clube local.[1] Em 2005, o atleta competiu em seu primeiro evento internacional, o Campeonato Internacional Japonês Júnior.[1] Dois anos depois, o ginasta entrou para a equipe masculina principal do país.[1] No mesmo ano, disputou a etapa de Copa do Mundo de Paris, conquistando a medalha de bronze no salto, e a nona colocação no solo.[2]
Em 2008, na etapa de Tianjin, fora medalhista de ouro nos exercícios de solo.[3] Em outubro do mesmo ano, em sua primeira aparição olímpica, nos Jogos Olímpicos de Pequim, o ginasta conquistou a medalha de prata na prova coletiva, superado pela equipe chinesa. No concurso geral, Kohei foi novamente medalhista de prata, ao não superar o anfitrião, Yang Wei, medalhista de ouro. Na final do solo, fora apenas quinto.[4] Como último evento do ano, deu-se a etapa de Madrid, da Copa do Mundo. Nele, fora medalhista de prata no solo, superado pelo brasileiro Diego Hypólito.[1]
Abrindo o calendário competitivo de 2009, disputou a etapa de Cottbus de Copa do Mundo, sendo medalhista de ouro nos exercícios de solo.[1] Em outubro, participou do Campeonato Mundial de Londres. No evento classificou-se para três finais: geral, solo e barra fixa. No geral, favorecido com a queda de outros ginastas, conquistou a medalha e ouro. No solo, só terminou em quarto, e na barra, foi sexto.[1] Como próximo compromisso, disputou a Copa Toyota, conquistando a medalha de ouro no solo e a prata na barra fixa.[5]