The puzzle was designed anonymously by Howard Garns, a 74-year-old retired architect and freelance puzzle constructor, and first published in 1979. Although likely inspired by the Latin square invention of Leonhard Euler, Garns added a third dimension (the regional restriction) to the mathematical construct and (unlike Euler) presented the creation as a puzzle, providing a partially-completed grid and requiring the solver to fill in the rest. The puzzle was first published in New York by the specialist puzzle publisher Dell Magazines in its magazine Dell Pencil Puzzles and Word Games, under the title Number Place.

The puzzle was introduced in Japan by Nikoli in the paper Monthly Nikolist in April 1984 as Suuji wa dokushin ni kagiru, which can be translated as "the numbers must be single" or "the numbers must occur only once". The puzzle was named by Kaji Maki, the president of Nikoli. At a later date, the name was abbreviated to Sudoku. In 1986, Nikoli introduced two innovations which guaranteed the popularity of the puzzle: the number of givens was restricted to no more than 32 and puzzles became "symmetrical" (meaning the givens were distributed in rotationally symmetric cells). It is now published in mainstream Japanese periodicals, such as the Asahi Shimbun. Within Japan, Nikoli still holds the trademark for the name Sudoku; other publications in Japan use alternative names.

In 1989, Loadstar/Softdisk Publishing published DigitHunt on the Commodore 64, which was apparently the first home computer version of Sudoku. At least one publisher still uses that title.

Yoshimitsu Kanai published his computerized puzzle generator under the name Single Number for the Apple Macintosh in 1995 in Japanese and English, for the Palm (PDA) in 1996, and for the Mac OS-X in 2005.

Bringing the process full-circle, Dell Magazines, which publishes the original Number Place puzzle, now also publishes two Sudoku magazines: Original Sudoku and Extreme Sudoku. Additionally, Kappa reprints Nikoli Sudoku in GAMES Magazine under the name Squared Away. The New York Post, USA Today, The Boston Globe, Washington Post, and San Francisco Chronicle now also publish the puzzle. It is also often included in puzzle anthologies, such as The Giant 1001 Puzzle Book (under the title Nine Numbers).

Within the context of puzzle history, parallels are often cited to Rubik's Cube, another logic puzzle popular in the 1980s. Sudoku has been called the "Rubik's cube of the 21st century".