A keresztrejtvény elődjének számító feladványok már a 19. századi Angliában megjelentek, 1873-tól az amerikai St. Nicholas gyermekmagazin hasábjain is felbukkantak. Olaszországban is volt ilyen próbálkozás, 1890. szeptember 14-én az Il Secolo Illustrato della Domenica magazin tett közzé egy függőlegesen és vízszintesen is 4-4 kockából álló, sötét kockák nélküli szóvadászatot Időtöltéshez címmel.
A mai értelemben vett keresztrejtvény megszületését hivatalosan 1913. december 21-ére datáljuk, szülőatyjának pedig a liverpooli származású Arthur Wynne-t tekintjük, aki a New York World magazin vasárnapi mellékletében tette közzé szókeresztezős játékát. A szórakozásrovatban megjelent feladványt egy középen üres, gyémánt alakú négyzethálóban helyezte el, alatta megadta a meghatározásokat, a fun szót segítségként előre beírta.
Keresztrejtvényei ezután heti rendszerességgel jelentek meg a magazin hasábjain, s más újságok is közölni kezdték a játékos kedvű olvasók körében gyorsan népszerűvé vált feladványokat. Az olvasók a helyes megfejtést keresve megrohamozták a könyvtárakat is, a New York-i közkönyvtár 1921-ben már arról panaszkodott, hogy a szótárakra és enciklopédiákra vadászó rejtvényfejtők elriasztják a kézikönyveket tanulásra használó diákokat, hozzátéve: a vezetőség kötelességének tekinti olvasásra jogosult látogatóinak védelmét.
Akadtak persze szkeptikusok, akik nem jósoltak nagy jövőt a gyermekjátékból felnőttek szenvedélyévé vált időtöltésnek. Több lapban viccekkel tették nevetségessé a rejtvényfejtést, de népszerűvé válását már semmi sem akadályozhatta meg. 1924-ben piacra dobták az első keresztrejtvény-könyvet, amely óriási sikert aratott, a crossword puzzle kifejezés 1930-ban a szótárba is bekerült. Legtovább a tekintélyes, igen konzervatív The New York Times című lap vonakodott, amely még ekkor is mint a lelkigyakorlat primitív formájáról cikkezett a rejtvényfejtésről, de végül 1942-ben beadta a derekát, és közölte első keresztrejtvényét. Jól tette, hiszen napjainkban a lap keresztrejtvényei a legnépszerűbbek az Egyesült Államokban.
A keresztrejtvények 1944-ben még a hadtörténetbe is bekerültek: a szövetséges csapatok hírszerzői (szintén rejtvényfejtők) megdöbbenve konstatálták, hogy a brit The Daily Telegraph keresztrejtvényeiben rendre feladványként szerepelnek a tervezett normandiai partraszállással kapcsolatos titkos kódnevek, sőt négy nappal a hadművelet megkezdése előtt éppen az egész akció fedőnevének választott overlord szót kellett megfejteni. A rejtvényeket összeállító középiskolai tanárt kihallgatták, de ártatlannak bizonyult. Csak négy évtized után derült ki, hogy a szavak a tanár egyik diákjának ötletére kerültek a rejtvénybe, aki a katonai táborok környékén lődörögve hallotta őket.
A keresztrejtvény 1925. január 22-én érkezett meg Magyarországra. A Ma este című lap hasábjain megjelent feladványt Kristóf Károly fiatal újságíró szerkesztette, miután meglátta az angol lapokban közölt négyzetrácsos feladatokat. A legenda szerint a kész rejtvényt szerette volna kipróbálni valakin, ezért leszaladt az EMKE-be, ahol egy fiatalember a verseskötetét árulta. Fölhívta a szerkesztőségbe, leültette, s elé tette a feladványt, de az a trükkös négyzetháló láttán azt mondta: „Van nekem elég rejtvény az életemben!”, azzal felállt és elment. A fiatalember ma már a magyar költészet halhatatlanja: József Attilának hívták. Kristóf Károly egyébként több keresztrejtvénnyel nem próbálkozott, de alapító tagként dolgozott az 1957-ben elindított Füles rejtvényújság szerkesztőségében.
A keresztrejtvény évszázados története során a rejtvénykészítők a feladványok számos típusát alakították ki (olasz, skandináv stb.), ki az egyikre, ki a másikra esküszik. A Guinness rekordok könyve szerint az eddigi legtermékenyebb rejtvénykészítő az angol Roger Squires, aki 2013. június 30-áig 74 634-et állított össze, ehhez körülbelül két és negyed millió magyarázatot adott meg. Ő tartja a keresztrejtvényben publikált leghosszabb szó rekordját is, a helyes megfejtéshez az 58 betűs walesi kisváros, Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch nevét kellett lebetűzni, amivel még a városka lakói sem boldogulnak egykönnyen.
