Este rompecabezas numérico puede haberse originado en Nueva York en 1979. Entonces, la empresa Dell Magazines publicó este puzzle, ideado por Howard Garns, bajo el nombre de Number Place (el lugar de los números).

Es muy probable que el sudoku se crease a partir de los trabajos de Leonhard Euler, famoso matemático suizo del siglo XVIII. Dicho matemático no creó el juego en sí, sino que utilizó el sistema llamado del cuadrado latino para realizar cálculos de probabilidades.

Posteriormente, la editorial Nikoli lo exportó a Japón, publicándolo en el periódico Monthly Nikolist en abril de 1984 bajo el título "Sūji wa dokushin ni kagiru" (数字は独身に限る), que se puede traducir como "los números deben estar solos" (独身 significa literalmente "célibe, soltero"). Fue Kaji Maki (鍜治 真起), presidente de Nikoli, quien le puso el nombre. Posteriormente, el nombre se abrevió a Sūdoku (数独; sū = número, doku = solo); ya que es práctica común en japonés tomar el primer kanji de palabras compuestas para abreviarlas.

En 1986, Nikoli introdujo dos innovaciones que garantizarían la popularidad del rompecabezas: el número de cifras que venían dadas estaría restringida a un máximo de 30 y los puzzles serían "simétricos" (es decir, las celdas con cifras dadas estarían dispuestas de forma rotacionalmente simtrica). Esto no siempre se cumple en los sudokus actuales. En 1997 Wayne Gould preparó algunos sudokus para el diario The Times, que los publicó bastante más tarde, en diciembre de 2004. Tres días después, The Daily Mail publicó sus sudokus con el nombre codenumber. En 2005 muchos otros periódicos de todo el mundo empezaron a incluir sudokus a diario en sus páginas.

En el año 2005, la ICPC (International College Programming Contest) incluyó entre sus 9 problemas el Sudoku.