Първата кръстословица в света е публикувана на 21 декември 1913 г. от англичанина Артър Уайн в неделното издание на вестник New York World. Уайн поддържал в изданието т.нар. забавна страница с гатанки, анаграми, картинки с разлики и други любопитни неща.
Идеята за кръстословицата „отлежавала“ в ума му от месеци и в навечерието на Коледа я поднесъл като подарък на читателите. Той начертал фигура с квадратчета във формата на диамант, написал в средата думата FUN (забавление) и започнал да измисля слова, в които има букви от първата дума. За по-голяма яснота номерирал квадратчетата и дал обяснителни бележки за откриване на правилните думи. Придружаващите инструкции били кратки и ясни: „Попълнете малките квадратчета с думи, които отговарят на описаните по-долу обяснения”. С течение на времето се появили ребуси в най-различни форми. Така главоблъсканицата бързо спечелила привърженици.
Единствената слабост на кръстословиците се оказали грешките, допускани от печатарските машини, които много често размествали или припокривали квадратчетата. Отчитайки този съществен недостатък, издателите на New York World спрели да поместват кръстословици. Веднага последвало силно недоволство на читателите, което ги принудило да възобновят страницата с ребуса само седмица по-късно.
Най-голямото признание за кръстословицата идва през 1924 г., когато американците Дик Саймън и Линкълн Шустър пускат на пазара книга, съдържаща всички кръстословици, публикувани в New York World. Изданието се превръща в хит на американския пазар и само за три месеца от него са продадени над 40 000 екземпляра.
