Se cree que la ciudad de Frontera sea la misma villa.

El conquistador español Hernán Cortés, quien fundó la villa, le puso ese nombre en honor a la victoria obtenida sobre los indígenas mayas justo el día de "la encarnación del Divino Verbo".

Sin embargo, no tuvo un gran desarrollo como otras ciudades coloniales debido a lo inhóspito que resultaba para los españoles vivir en un territorio cubierto de selvas, agua y grandes pantanos, además que en el territorio no existían metales preciosos, por lo que una vez conquistado Yucatán en 1542, Montejo trasladó los poderes hacia la recién fundada ciudad de Mérida.

Un año más tarde Cortés envía a Baltasar de Osorio Gallegos, quien también fracasa en lograr la pacificación.

En 1537 ante la inestabilidad existente en Tabasco y Yucatán, Francisco de Montejo solicita apoyo de la Corona española, por lo que la Reina Juana I emite una real cédula nombrando a Montejo como gobernador Tabasco, Yucatán y Honduras, por lo que el "Adelantado" se traslada a Honduras para lograr su pacificación.

En 1557 comienzan las incursiones piratas en las costas tabasqueñas, asentándose los piratas en la isla de Tris (hoy isla del Carmen) y convirtiéndose en un verdadero azote para la capital de la Provincia.

En varias ocasiones los piratas saquean, incendian y destruyen la ciudad, sembrando el terror entre sus habitantes, lo que provoca que algunos vecinos se vayan de la ciudad remontando el río Grijalva hasta llegar a un lugar que tenía tres lomas, estableciéndose ahí y nombrándole San Juan Bautista de Villahermosa.

Años más tarde se le cambiaría el nombre por el de San Juan Bautista.

Los españoles ocupaban la "loma" y los indios las partes bajas de los laboríos (indígenas dedicados a la agricultura) y los naboríos (indígenas que servían en las casas de los encomenderos).

Esta elevación sobre el suelo, servía para evitar la entrada del agua del río a las viviendas debido a las recurrentes inundaciones que año con año azotaban la villa.

Además de ser un lugar para reparar y construir embarcaciones.

En el mercado se realizaba también la venta del tributo de las encomiendas de la Corona Española: maíz, gallinas, comales, petates, mantas, y la de los indios y comarcanos particulares: frijol, calabaza, plátano, ají, tomates, legumbres, raíces, pescados, fruta, cántaros, jarros y carne.

Posteriormente, la precaria población es destruida e incendiada por los naturales y Cortés después de conocer la difícil situación en que vivían sus habitantes, envió en 1525 a Juan de Vallecillos, quien reconstruyó la villa.

Sin embargo, este crecimiento, se vería interrumpido en 1557 cuando los primeros ataques piratas hicieron su aparición, convirtiéndose en un verdadero azote no solo para la villa, sino para toda la Provincia de Tabasco.

[5]​ Se calcula que hacia 1579 la población de la villa sobrepasaba los 370 habitantes.

Posteriormente, ante la negativa a la solicitud anterior, y como los ataques piratas no cesaban, y continuamente destruían y saqueaban la villa, en 1619 vuelve a gestionarse el traslado de los poderes ante el Virrey Diego Fernández de Córdoba, quien lo autoriza con fecha 3 de diciembre de ese mismo año, sin embargo, el traslado no se realizó debido a que muchos vecinos no quisieron abandonar la villa.