First modern Naughts and Crosses/Tic Tac Toe?
Having spent a little while looking into this, the only clear thing is that there is no firm evidence for any distant historical first date for Tic Tac Toe. Although many people claim the Romans played this game, in the form of Terni Lapilli, and point to the large number of historical boards that exist, scratched into walls, this seems unlikely, not least because Tic Tac Toe isn't a very interesting game:


  Terni Lapilli is considered to be identical to modern Tic-Tac-Toe.
  However, although Terni Lapilli boards are found throughout the
  Empire, scratched on walls, floors, and roofs, no X's and O's
  accompany the markings. Obviously playing pieces were being used for
  this game and the would surely be the same ones used for both
  Latrunculi and Tabula. Bolesden says that three pieces were used in
  this game but if that is true, this is not Tic-Tac-Toe.
  
  Judging from the number of Terni Lapilli boards found around Rome it
  would seem this game was more popular than Tic-Tac-Toe, and therefore
  we must conclude that it was not, in fact, Tic-Tac-Toe since this is
  not really a game and could not sustain such interest.


Three Men's Morris, on the other hand, which uses an identical board, is much more challenging, and has a board from Egypt dated to 1400 BCE.

One suggestion is that the etymology of "Tic-Tac-Toe" is based on "Tit-Tat-Toe" (as in tit-for-tat retaliation), apparently from the 16th Century, but this is completely unsubstantiated.

Wikipedia's information, dated definitively to 1864 and widely re-gurgitated across the internet, is based on the OED, which quotes a Boston periodical, The Living Age:


  1864   Littell's Living Age 22 Oct. 182/1   Mr Babbage..has proceeded
  some way towards the invention of an automaton intended to play at the
  very simple game called indifferently ‘noughts and crosses’ or
  ‘tit-tat-to’.


You can read the full reference for yourself online: The Living Age, 22 October 1864, p.182.

It is known is that there are many historical examples of so-called "games of alignment", from all around the world:


  ...in Europe, Asia, and Africa many people have long been playing similar
  games which require the alignment of five or nine symbols in a row.
  Most of these latter games are played on boards scratched in the
  earth, carved into wooden or stone benches, or cardboard or wooden
  boards constructed for these variations. There are at least nine
  different board configurations for these games.
  
  These games are grouped together because they all have the same
  purpose - that is for two players to each place a symbol on the board,
  one symbol at a time during alternate turns of play, with the goal of
  aligning a series of agreed upon symbols in a "row", while at the same
  time attempting to prevent the other player from doing the same thing.
  In each version of the game, as the number of symbols are increased,
  the goal does not change, nor does the primary mode of play. In
  versions using five or nine symbols, additional procedures are added
  to the play of the game.


It seems very likely that the game existed in the distant past, but being a less than engrossing pastime for anyone other than young children, distant historical references are lacking.

Key references for further research:


H.J.A. Murray, A History of Board Games Other Than Chess
Claudia Zaslavsky, Tic Tac Toe: And Other Three-In-A Row Games from Ancient Egypt to the Modern Computer
R.C. Bell, Board and Table Games from Many Civilizations
An extensive bibliography of books covering board game history
Many links to period board game references and reconstructions