Carrière
Il fait ses débuts sur la scène internationale à l'occasion des Jeux africains de 2003, s'adjugeant le titre du 1 500 m devant son compatriote Robert Rono. Sélectionné pour les Championnats du monde de Paris, Paul Korir échoue au pied du podium, à trois dixièmes de seconde seulement de l'Ukrainien Ivan Heshko, médaillé de bronze. Il établit lors du Meeting de Bruxelles la meilleure performance de sa carrière sur 1 500 m en 3 min 30 s 72, et remporte par ailleurs la Finale mondiale d'athlétisme à Monaco.
En début d'année 2004, Paul Korir remporte son premier titre international majeur à l'occasion des Championnats du monde en salle de Budapest. Il s'impose au sprint, sur 1 500 m, avec le temps de 3 min 52 s 31, devançant Ivan Heshko et Laban Rotich. En , le Kényan remporte les Championnats d'Afrique à Brazzaville.