Tras su paso por Italia bajo las órdenes de Don Gonzalo Fernández de Córdoba, Gonzalo Guerrero decidió cruzar el charco. Ya al otro lado del Atlántico, en 1510, Guerrero formó parte de la tripulación del gobernador de Veragua (actual Panamá), Diego de Nicuesa, que estaba destinada a continuar con la colonización iniciada pocos años antes en La Española, la actual Cuba. El problema fue que una tormenta durante el camino desvió todos los planes y la nave en la que Gonzalo Guerrero se hallaba terminó naufragando cerca de Jamaica.

Tras el desastre, tan solo 20 hombres, entre los que se encontraba Gonzalo Guerrero, lograron salvarse a bordo de una pequeña embarcación con la que quedaron a merced de las mareas, las cuales les llevaron a la Península de Yucatán. Aquella travesía no resultó nada sencilla, pues algunos de los supervivientes españoles perecieron antes de que su vista alcanzase a ver la costa. Sin embargo, para los que se mantenían con vida lo peor solo estaba a punto de comenzar, y es que los que resistieron la travesía acabaron siendo prisioneros de una de las tribus mayas del lugar.

Tiempo después, tan solo dos españoles de aquel grupo de supervivientes habían logrado permanecer con vida, se trataban de Gerónimo de Aguilar y Gonzalo Guerrero. El resto habían sido sacrificados, devorados, asesinados o muerto por culpa de las enfermedades o el agotamiento. Sea como fuere, tanto Gerónimo de Aguilar como Gonzalo Guerrero fueron tratados como esclavos y vendidos de cacique en cacique. Fue en ese tiempo cuando Gonzalo Guerrero, a diferencia de su compañero, empezó a asimilar la cultura de sus captores, y no solo eso, también comenzó a ganarse la confianza de varios caciques al enseñarles diversas técnicas de combate aprendidas en el campo de batalla que le otorgaron gran prestigio hasta el punto de ser consejero de guerra. No obstante, Gonzalo Guerrero seguía privado de su libertad.

Así fue hasta que un día salvó al jefe maya Balam cuando este fue atacado por un caimán. Aquello le otorgó finalmente la libertad  a Gonzalo Guerrero y, aunque pudo volver con sus compatriotas españoles, este decidió formar parte de varias expediciones mayas.

Pronto, sus hazañas en los campos de batalla le otorgaron el rango de ‘Nacom’, es decir, jefe maya, y contrajo matrimonio con la princesa Zazil Há. Además, Gonzalo Guerrero se hizo los tatuajes y las mutilaciones propias de aquella cultura y asimiló los rituales mayas, llegando a sacrificar a alguno de sus hijos.