Like the origin of playing cards, the origin of patience is uncertain. The game is most likely German or Scandinavian in origin. It became popular in France in the early 19th Century reaching England and America in the latter half. Patience was first mentioned in literature shortly after cartomantic layouts were developed circa 1765. The earliest known recording of a game of patience occurred in 1783 in the German game anthology Das neue Königliche L'Hombre-Spiel. Before this, there were no literary mentions of such games in large game compendiums such as Charles Cotton's The Compleat Gamester (1674) and Abbé Bellecour's Academie des Jeux (1674).

There is an old tradition in the German or Scandinavian countries to use "patience" as a guide to what the near future has to offer, a kind of "luck" meter. This belief assumes that a person’s "luck" will vary from time to time and important matters should not be initiated or conducted when the cards are not favorable. If there are no winnings in the game for a number of tries it spells caution in what you do. If a win at the first try times are good and “luck” smiles at you, thus the immediate future can be used for important decisions. Timing the game is a further indicator of the strength of the outcome.

Napoleon was said to have "played patience" during his exile; however from written accounts, he played Vingt-Un, Piquet, and Whist but not Patience. The story is thought to have arisen from a misinterpretation. Nonetheless, many solitaire games were named after him, such as Napoleon at St. Helena, Napoleon's Square, etc.

The first collection of solitaire card games in the English language is attributed to Lady Adelaide Cadogan through her Illustrated Games of Patience, published in about 1870 and reprinted several times. Other collections quickly followed such as Patience by E. D. Cheney, Amusement for Invalids by Annie B. Henshaw (1870), and later Dick's Games of Patience, published by Dick and Fitzgerald. Other books about solitaire written towards the end of the 19th century were by H. E. Jones (a.k.a. Cavendish), Angelo Lewis (a.k.a. Professor Hoffman), Basil Dalton, Ernest Bergholt, and Mary Whitmore Jones.