also criss-cross, 1833, "a checked pattern in cloth," 1848, "a crossing or intersection," from Middle English crist(s)-crosse (early 15c.), earlier Cristes-cros (c. 1200) "the Cross of Christ," also "the sign of the cross," from late 14c. often "referring to the mark of a cross formerly written before the alphabet in hornbooks. The mark itself stood for the phrase Christ-cross me speed ('May Christ's cross give me success'), a formula said before reciting the alphabet" [Barnhart]. It has long been used without awareness of its origin.
How long agoo lerned ye, 'Crist crosse me spede!'
Have ye no more lernyd of youre a b c,
[Lydgate, "The Prohemy of a Marriage Betwix an Olde Man and a Yonge Wife," c. 1475]
It is attested from 1860 as an old name for tic-tac-toe. As an adjective, by 1846. As a verb, by 1818.