1913.gada 21.decembrī Ņujorkas laikrakstā iznāk pirmā krustvārdu mīkla. Tās autors ir Artūrs Vains. Lieki piebilst, krustvārdu mīkla nebūt nebija pirmā pasaulē, jo šāda veida prāta uzdevumus izmantoja jau krietni senāk. Tomēr Vains bija pirmais, kurš izmantoja nosaukumu vārdu krusts, kas vēlāk pārtapa par krustvārdu mīklu.

Iespējamais pirmais brīdis, kad kāds ir sācis izmantot krustvārdu mīklas un arī tāda veida nosaukumu ir ievērojami izstrīdēts. Zināms, ka dažāda veida atjautības uzdevumus, kur jāsavieno izlaisti burti, simboli vai bildītes, izmantoja daudzās zemēs. Pirms Artūra Vaina, pilnīgi droši var teikt, ka krustvārdu mīklām līdzīgus uzdevumus sastādīja gan Anglijā, gan Itālijā, gan arī ASV un Āzijas valstīs. Āfrikā izteikta bija Dienvidāfrikas krustvārdu mīkla, kas lielā mērā bija tā pati angļu mīkla, jo Anglijas koloniālā vara izpletās teju pa visu pasauli, tāpēc arī ietekme bija plaša. Tomēr īpaši pieminama ir līdzīgu mīkla parādīšanās periodiskos izdevumos ASV jau 18.gadsimta beigās un Itālijā 19.gadsimta beigās.

Zināms, ka 1890.gadā Itālijas ikdienas laikrakstā parādījās mīklas ar vārdiem, kuras sauca par laika īsināšanas mīklām. Šīs mīklas, kuras sauca par „Per passare il tempo” autors bija Džuzepe Eroldi. No mūsdienu izplatītākajām mīklām tās atšķīrās tikai ar to, ka tām bija romba forma un nebija aizkrāsoto lauciņu. Eroldi savas mīklas veidoja tā, ka katra vārda burti skāra blakus esošos vārdus.

Anglijā krustvārdu mīklas bija savdabīgs bērnu atjautības uzdevums, kuru plaši sāka izmantot skolās 19.gadsimtā. tās bija lielā mērā līdzīgas itāļu variantam, jo arī bija daudz maz kvadrāta vai romba formā un viena vārda burti bija nozīmīgi citu vārdu burtiem. Šos uzdevumus izmantoja, lai bērniem trenētu spēju risināt uzdevumus un lai mācītu jaunus vārdus. Tomēr klasiskajā izpratnē krustvārdu mīklas parādījās ASV 1913.gada 21.decembrī.

Artūrs Vains bija brits, kurš pārcēlās uz dzīvi ASV. Viņa tēvam bija piederējis laikraksts tāpēc Vains jau agrā bērnībā bija iemācījies lasīt un izmantot dažādas vārdu spēles kā atjautības uzdevumus. Pats viņš bija armijas virsnieks un žurnālists un iespējams tāpēc aizrāvās ar krustvārdu mīklu minēšanu un vēlāk sastādīšanu, lai īsinātu laiku dienestā. Zināms, ka 1913.gadā viņš sastādīja krustvārdu mīklu laikrakstam “New York World”. Tieši Artūrs Vains bija pirmais, kurš nosauca šo mīklu par vārdi krustā jeb no angļu valodas – 'words in a cross'. Vēlāk šīs mīklas atvasināja jau citi laikraksti un tad novienkāršoja izteicienu līdz krustvārdu mīklai jeb vienkārši 'crossword'.

Īsts krustvārdu mīklu bums sākās 20.gadsimta pirmajā pusē. Laikraksti piedzīvoja īstu renesansi. Visi, kam nebija slinkums, drukāja kaut kādas avīzes un meklēja līdz ar to iespējas kā izklaidēt publiku. Pirmie lielie laikraksti, kas pārņēma šo atjautības uzdevumu publicēšanu, bija “Pittsburgh Press” un “Boston Globe”. 20.gados krustvārdu mīklas jau kļuva tik populāras, ka dažkārt to dēļ pat pirka avīzes. Karikatūrās smējās, ka lasītājs ir gatavs dzīties pakaļ pa vējam aizpūstai avīzei tikai tāpēc, ka krustvārdu mīkla vēl palikusi neatrisināta. Fenomens kļuva tik liels, ka Ņujorkas bibliotēkas pat ziņoja, liela daļa lasītāju nāca uz bibliotēku, lai tikai varētu atrisināt avīzēs esošās krustvārdu mīklas.

1933.gads kļuva par zinātnisku brīdi arī pašam jēdzienam „krustvārdu mīkla”, jo tieši šajā gadā to iekļāva Oksfordas angļu valodas vārdnīcā. Savukārt praktisko pielietojumu krustvārdu mīklas pnodemonstrēja Otrā Pasaules kara laikā. Ignorējot faktu, ka krustvārdu mīkla palīdz trenēt smadzenes jebkuram tās risinātājam, Otrā pasaules kara laikā krustvārdu mīklas izmantoja arī slepenu ziņojumu nodošanai. Slavenā Blečlī parka darbinieki, kuri kodēja vācu Enigmas sūtītās ziņas, tika atlasīti pēc tā, cik ātri risināja krustvārdu mīklas. Tikmēr sabiedroto spēku slepenajai saziņai Normandijas iebrukumam, operācijas “Overlord” ietvaros kodētās ziņas sūtīja iestrādātas krustvārdu mīklās.