The discovery in the state of Veracruz of a block inscribed with symbolic shapes has astounded anthropologists.
Researchers tell Science magazine that they consider it to be the oldest example of writing in the New World.
The inscriptions are thought to have been made by the Olmecs, an ancient pre-Colombian people known for creating large statues of heads.
Co-author Stephen Houston of Brown University in Providence, Rhode Island, US, said it was a "tantalising discovery".
"I think it could be the beginning of a new era of focus on Olmec civilisation," he said.
"It's telling us that these records probably exist and that many remain to be found. If we can decode their content, these earliest voices of Mesoamerican civilisation will speak to us today."
The slab has been dated to the early first millennium BC. It appears to have been made by the Olmec civilisation of Mesoamerica, a geographical region located between the Sinaloa River valley in northern Mexico and the Gulf of Fonseca south of El Salvador.
The area, once home to the Aztecs, Mayas and their predecessors, covers much of Mexico, Guatemala, Belize, El Salvador, and western Honduras.
The Olmecs appeared on the coast of the Gulf of Mexico around 1,200 BC. They are known to have carved glyphs - a symbolic figure or character that stands for a letter, sound, or word - since around 900 BC, but scholars are divided over whether this can be classified as true writing.
The stone slab, named the "Cascajal block", was first uncovered by road builders digging up an ancient mound at Cascajal, outside San Lorenzo, in the late 1990s.
It weighs about 12kg (26lbs) and measures 36cm (14in) in length, 21cm (8in) in width and 13cm (5in) in thickness. Its text consists of 62 signs, some of which are repeated up to four times.
Mexican archaeologists Carmen Rodríguez and Ponciano Ortíz were the first to recognise the importance of the find, and it was examined by international archaeologists earlier this year.
The team says the text "conforms to all expectations of writing" because of its distinct elements, patterns of sequencing, and consistent reading order.
Commenting on the discovery, Mary Pohl, of Florida State University in Tallahassee, said she believed the authors had made a good case.
"I think it's a hugely important and symbolic find," she told the BBC News website. "It's new and further evidence that [the Olmecs] had writing and had text."
The block was carved from precious serpentine rock, suggesting it was probably a holy object used by high orders of society for some kind of ritual activity, she said.
The inscription is indecipherable but scientists hope that further excavations at the site could give clues to its content.
"I think more things will be found," said Dr Pohl. "We can make some progress although I don't think we'll ever be able to decipher it completely."
The Sumerians, who lived in Mesopotamia, what is now southern Iraq, are generally regarded to be the first people to develop a form of writing around 5,000 years ago; although there have been even older claims made for Chinese inscriptions.