Los orígenes de Nautla, se remontan a la época prehispánica, cuando era un pueblo, que estuvo situado, en lo que actualmente es Casitas, formaba parte de un grupo de totonacas localizados entre Tlapacoyan y lo que actualmente es Vega de Alatorre; tras la irrupción de pueblos provenientes del norte de recolectores y cazadores, muchos pueblos abandonaron la costa en busca de sistemas que por naturaleza ofreciera elementos para su defensa, ante la amenaza militarista que traían. en la desembocadura del Nautla, quedaron solo pueblos diseminados, que desde el año 1200 recibieron la influencia de los Mexicas.
En 1519 arriban a Villa Rica 500 españoles al mando de Hernán Cortes, incursionan hacia Zempoala y allí son recibidos por un cacique llamado Cuauhtlaevana a quien le llamaron el cacique gordo; Quien los recibió de buena manera y hasta con regalos.
En Nau-Tlan (cuatro lugares) gobernaba Cuauhpopoca a nombre de Moctezuma y era el encargado de cobrar los tributos en toda la región. Juan de Escalante, quien quedo como responsable en Zempoala, mientras Cortes viajaba a negociar con Moctezuma, trata de negociar con Cuauhpopoca, lo cual no logro dando lugar a una gran batalla entre los mexicas de Cuauhpopoca y los alidos españoles totonacos.
Resultando de la batalla las muertes de Juan de Escalante y cinco de sus soldados y la quema del pueblo de Nautla que se conformaba de casas de madera y techos de palma. Cuauhpopoca viaja a Tenochtitlan con su hijo y quince soldados llevando la cabeza de un soldado de apellido Arguello para entregarla a Moctezuma, quien ya se encontraba sometido por Cortes lo culpo de la matanza de Nautlan y lo hizo preso formalmente a la vez que sacrificaba a Cuauhpopoca y los suyos quemándolos vivos.
Nautla cuenta también con antecedentes muy importantes de su participación en la lucha por la independencia de México. Ya que las fuerzas armadas insurgentes al mando de José María Morelos y Pavón enviaron a este puerto a un grupo comandado por Guadalupe Victoria, quien encontró aquí un puerto natural alternativo para poder negociar armas, pertrechos de guerra, municiones y víveres para las fuerzas insurgentes.
De lo anteriormente dicho existen en la cabecera municipal como muestra tres cañones que fueron encontrados cerca de la playa y cuyo origen según un experto de National Geographic son del siglo XVI y fabricados en Inglaterra (Estos cañones ya tienen su registro en el INAH como patrimonio histórico de esta ciudad y puerto).
Durante la época Colonia, el territorio costero cercano al río Nautla, se fue desarrollando, así surgieron estancias ganaderas, que para 1567 eran 18, entre Cempoala y Tecolutla. El cultivo de la caña de azúcar se fue extendiendo a lo largo del camino y en 1568 ya mostraba una fisionomía de pueblo.
Una vez consumada la independencia de México, en 1828, y bajo el gobierno de Guadalupe Victoria, se habilitó para el comercio la barra de nautla, mejorando así las condiciones de vida y desarrollando la actividad pesquera, que ya desde antes se daba; gran parte de la historia del municipio está ligada Jicaltepec, una localidad ubicada en este municipio y que recibió a una colonia francesa entre 1832 y 1846, cuando llegaron tres grupos de inmigrantes, la primera de ellas en 1833, que traía con sigo a 80 colonos, quienes llegaron a vivir al pueblo, en el cual existían pequeñas casa de madera y estaba habitado ya por algunos indígenas. En septiembre de 1834 zarpó otro barco con 100 borgoñeses de Champlitte, y en abril de 1835 otra con 112, la última se dio en 1840. Los colonos se diseminaron por toda Nautla, Paso Largo, El Pital, Paso de Telaya y Paso de Novillos, instalándose de esta forma las familias Sempé, Levet y Mothelet.