Το πρώτο σταυρόλεξο δημοσιεύτηκε στις 21 Οκτωβρίου του 1913 στην εφημερίδα «Κόσμος της Νέας Υόρκης». Δημιουργήθηκε από τον Άρθουρ Γουάιν, έναν άγγλο δημοσιογράφο που επιμελείτο τη σελίδα ψυχαγωγίας της εφημερίδας. Αφού είχε εξαντλήσει και ανακυκλώσει όλα τα διαθέσιμα παζλ της εποχής εκείνης, δημιούργησε ένα γρίφο σε σχήμα ρόμβου, που έμοιαζε αρκετά με το σημερινό σταυρόλεξο.
Ο Γουάν δεν πίστευε στα μάτια του, όταν την επομένη της κυκλοφορίας της η εφημερίδα κατακλύστηκε από εκατοντάδες γράμματα αναγνωστών, που ζητούσαν επιτακτικά και νέα σταυρόλεξα. Η σταυρολεξομανία είχε αρχίσει, κι έφθασε στο αποκορύφωμά της στην Αμερική μετά το τέλος του Α' Παγκοσμίου Πολέμου.
Στις 2 Νοεμβρίου του 1924 η τρέλα περνά τον Ατλαντικό και φθάνει στην Ευρώπη, με τη δημοσίευση του πρώτου σταυρολέξου από την αγγλική εφημερίδα «Sunday Express». Τη δεκαετία του '30 άρχισε να διαδίδεται με ταχύτητα σε όλα τα μήκη και πλάτη της Γης και στη χώρα μας.
Στον B' Παγκόσμιο Πόλεμο πολλοί άγγλοι σταυρολεξάδες χρησιμοποιήθηκαν από τις συμμαχικές υπηρεσίες αντικατασκοπίας για να σπάνε τους κώδικες των ναζί.
Στις μέρες μας, το σταυρόλεξο αποτελεί μία σταθερή αξία. Το βρίσκουμε παντού, από τις εφημερίδες και τα εξειδικευμένα περιοδικά, ως το διαδίκτυο. Οι γιατροί πιστεύουν ότι κάνει καλό στην υγεία, καθώς «ακονίζει» το μυαλό και συμβάλλει στην αποφυγή δυσάρεστων καταστάσεων τύπου Αλτσχάιμερ.