Los asentamiento humanos en lo que es hoy el territorio del municipio de Nacajuca debe remontarse al momento en que las grandes urbes mayas del clásico y del clásico tardío como Palenque, Tikal, Uxmal, Bonampak, Reforma, Pomoná y Comalcalco fueron abandonadas.

Los investigadores han encontrado indicios de que parte de la población de esas grandes urbes siguiendo el cauce los ríos, se estableció en la planicie de Tabasco y en la zona costera del Golfo de México.

A la llegada de los españoles en 1518 los mayas chontales ocupaban el delta de los ríos Mezcalapa, Grijalva y Usumacinta.

Los pueblos de Nacaxuxuca, Túcta, Mazateupa, Tapaucingo, Huatacalca, Tecoluta, Huaitalpa, Olcuatitlan y Ohicake, son antiquísimos y datan de las primeras emigraciones de las tribus de la península de Yucatán, den norte de Chiapas así como del Petén guatemalteco.

Durante la conquista, las primeras noticias que se tienen de este territorio datan de fines de 1524 y principios de 1525 cuando el conquistador Hernán Cortés en su viaje a las Hibueras (hoy Honduras), pasó por el territorio que hoy comprende este municipio; en su itinerario tocó una población que él llama de Anaxuxuca, como lo demuestra este extracto de su relación al Rey de España:

"...Esta provincia de Cupilcon es abundosa de esa fruta que llaman cacao y de otros mantenimientos (...)y mucha pesquería; hay en ella diez o doce pueblos buenos, digo cabeceras, como este de Anaxuxuca, es tierra muy baja y de muchas ciénagas, tanto que en tiempo de invierno no se puede andar, ni se sirven sino en canoas, y pasarla yo en tiempo de secas se hicieron más de cincuenta puentes..."

Hernán Cortés "Quinta Carta de Relación" De la Ciudad de Tenuxtitan, a 3 de septiembre de 1526 años.
El cronista Bernal Díaz del Castillo quien también acompañó a Cortés en dicho viaje, menciona haber pasado por un poblado llamado Nacaxuxuca, que en lengua náhuatl quiere decir "lugar de caras pálidas o descoloridas" en clara alusión a los habitantes del pantano que eran presa fácil del paludismo, por la abundancia de mosquitos que proliferan en estas regiones.

"...llegamos a otro gran pueblo que se dice Copilco y desde allí cominenza la provincia que llaman la Chontalpa y es toda muy poblada y llena de huertas de cacao, y muy de paz. Y de este Copilco, pasamos a Nacaxuxuca o Nacajujuyca y continuamos el camino a Zaguatán...Bernal Díaz del Castillo. Historia Verdadera de la Conquista de la Nueva España"

En 1528, con la llegada de Francisco de Montejo a Tabasco, comienza la campaña para pacificar completamente la provincia y sus esfuerzos se centran principalmente en la región de la Chontalpa, aunque con muy pocos resultados.

Es de destacar, la importancia de la ayuda que prestaron los habitantes del poblado de Túcta que ayudó mucho a los españoles a pacificar esta tierra, en aquella ocasión, el Rey de España, agradeció a sus habitantes con un cuadro en el que está pintada la corona real y que fue colocado en la iglesia del pueblo.
Por este motivo, a Túcta, se le llamaba en esa época: pueblo de la Corona de Túcta.

A partir de 1550, cuando la pacificación se iba logrando en la provincia, los españoles comenzaron a internarse y a vivir en los pueblos de Nacaxuxuca, Túcta, Mazateupa, Tapaucingo, Huatacalca, Tecoluta, Huaitalpa, Olcuatitlan y Ohicake, estableciendo encomiendas y fincas para la explotación del cacao y otros frutos.

El 10 de abril de 1579, durante una visita a Nacajuca, Vasco Rodríguez, alcalde mayor de Tabasco ordena a Melchor Alfaro Santa Cruz, hacer el primer mapa de la provincia de Tabasco y redactar una memoria para enviar a España.

De acuerdo a informes del gobierno colonial de Tabasco, en 1665 el partido de Nacajuca contaba con 13 pueblos.

El 31 de julio de 1843, las autoridades de San Pedro Nacajuca, juraron las Bases Constitucionales sancionadas por el presidente, general Antonio López de Santa Anna.

El 23 de mayo de 1844, Manuel Antonio León, prefecto de Nacajuca y el coronel Manuel Plasencia, forman una compañía de voluntarios para combatir la invasión a Tabasco que encabeza el coronel Francisco de Sentmanat y Sayas.

El 15 de julio de 1845, el Ayuntamiento de Nacajuca levanta acta reconociendo como presidente de la república al general Juan José Herrera y como gobernador a Juan de Dios Salazar.

El 17 de noviembre de 1852 conforme a un decreto del congreso del estado, el partido de Nacajuca lo componen además del pueblo de Nacajuca, cabecera del partido, los pueblos siguientes: Tucta, Mazateupa, Tapotzingo, Guatacalca, Tecoluta, Guaytalpa, Olcuatitán, Oxiacaque, con todas sus riberas, haciendas y rancherías.

En 1863, por decreto del congreso del estado, el pueblo de Nacajuca fue elevado a la categoría de villa, siendo gobernador del estado Victorino Dueñas Outruani.

En enero de 1971, el gobernador Mario Trujillo García, sancionó el decreto en que la villa de Nacajuca fue elevada al rango de ciudad.