En el territorio de lo que hoy son los estados de Tabasco y Veracruz, floreció la cultura Olmeca; considerada la "madre" de la civilización mesoamericana. Surgió hacia el 1500A.C., cuando pequeños grupos de agricultores se asentaron en las costas veracruzanas y tabasqueñas del Golfo de México, desarrollaron un calendario y un sistema de numeración, los cuales sentaron la base para el posterior desarrollo del calendario maya; igualmente desarrollaron un estilo artístico que se distingue por la monumentalidad y la representación de personajes religioso-militares con rasgos deformes. La cultura olmeca alcanzó su apogeo a partir del 1200A.C., teniendo como centro cultural y religioso a la ciudad de La Venta, ubicada en un islote de 5km², rodeado de pantanos, en el municipio tabasqueño de Huimanguillo. En esta ciudad se encuentra la que está considerada como la pirámide más antigua del nuevo mundo, la Pirámide Principal; en La Venta también se encontraron algunas cabezas colosales, características de esta cultura.

Otros sitios importantes de esta cultura se hallan en Veracruz, San Lorenzo y Tres Zapotes son los más relevantes. La decadencia de la cultura Olmeca comenzó hacia el 600A.C, desapareciendo completamente hacia el 100A.C.; sin embargo, legaron a las culturas posteriores, mayas y zoques; la construcción de pirámides, el calendario, la numeración y el cero, la escultura monumental y la talla en piedra, jade y cristal de roca. Posteriormente a los olmecas, en Tabasco se asentaron también grupos mayas y zoques.

El primer español que descubrió la región que hoy comprende el estado de Tabasco, fue el conquistador Juan de Grijalva, quien el 8 de junio de 1518 arribó a la desembocadura de un gran río al que puso el nombre de río Grijalva. El conquistador Hernán Cortés arribó a Tabasco el 12 de marzo de 1519 y después de derrotar en una cruenta batalla conocida como la "Batalla de Centla", a los naturales del pueblo de Potonchán, fundó el 25 de marzo la Villa de Santa María de la Victoria, que sería la primer población española en territorio continental de América. Ese mismo día, el presbítero Fray Bartolomé de Olmedo ofició la primer misa cristiana del continente, y los naturales obsequiaron a Cortés 20 mujeres, entre las cuales estaba Marina la Malinche, pieza clave en la conquista del imperio Azteca.

En 1525 Juan de Vallecillo se convierte en el primer gobernador de la naciente provincia de Tabasco, pero fracasa en lograr su pacificación. En 1529 Francisco de Montejo es nombrado gobernador de la Provincia de Tabasco, quien es encargado de su pacificación y desde aquí inicia la conquista de Yucatán. Pese a ser la primer posesión de la corona española en México, los conquistadores tardaron más de 40 años en pacificar la provincia debido a la férrea resistencia de los aborígenes. Una vez lograda la paz, Tabasco es anexado a la Capitanía de Yucatán. Abandonado por las autoridades de la corona, la provincia de Tabasco durante más de 100 años, es azotada por los piratas quienes destruyen las principales poblaciones.