Keres aprendió el ajedrez por su padre y su hermano mayor Harald (luego un destacado físico).
También en 1935 Keres saltó a la gran fama mundial cuando compitió exitosamente en la Olimpiada de ajedrez de Varsovia (Polonia), después de ello participó en varios torneos internacionales y logró triunfos sobre grandes maestros como José Raúl Capablanca y Reuben Fine, logrando inclusive empatar con el entonces campeón mundial Alexander Alekhine.
En 1938, Keres participó en el Torneo AVRO, donde participaban los ocho mejores jugadores de la época, obteniendo el primer lugar sobre los demás jugadores: Alexander Alekhine (campeón mundial vigente), José Raúl Capablanca y Max Euwe (excampeones), Mijaíl Botvinnik (futuro campeón mundial) y como retadores Reuben Fine, Samuel Reshevsky y Salo Flohr.
Keres jugó su primer campeonato soviético ese año en Moscú (URSS-12), ocupando el cuarto lugar (+9−4=6) delante de Mijaíl Botvinnik, entre otros.
En paralelo, Keres ganó tres veces el Campeonato de Ajedrez de la URSS en los años 1947, 1950 y 1951, derrotando en cada ocasión a jugadores de muy grande talento como Efim Geller, Tigran Petrosian, Vasili Smyslov, Mijaíl Botvinnik, Yuri Averbakh, David Bronstein, Mark Taimanov, Salo Flohr, Igor Bondarevsky, y Alexander Kotov.
A su funeral en Tallin acudieron cien mil personas, entre ellos el presidente de la FIDE y excampeón mundial Max Euwe.
En su larga carrera de casi 40 años, Keres derrotó en torneos oficiales a 8 de los 9 campeones mundiales de ajedrez con quienes se enfrentó, desde Capablanca hasta Bobby Fischer, siendo el único ajedrecista en lograr tal récord, pues las dos veces que jugó contra el futuro campeón Anatoli Karpov la partida acabó en tablas.
Otros grandes maestros contra los cuales Keres tuvo récord favorable fueron Reuben Fine, Salo Flohr, Viktor Korchnoi, Efim Geller, Savielly Tartakower, Mark Taimanov, Milan Vidmar, Svetozar Gligorić, Isaac Boleslavsky, Efim Bogoljubov y Bent Larsen.
Se ha erigido una estatua de Paul Keres en Tõnismägi, Tallin, la capital estonia.