Además de una pequeña fuerza de soldados españoles, lo acompañaba una mujer que se convertiría en su intérprete y en su amante y que tendría un protagonismo singular en la conquista española de México: Malintzin, más conocida como doña Marina o la Malinche.
Malinche, por llamarla por su nombre castellanizado, nació en el estado mexicano de Veracruz, en la costa de Yucatán, y pertenecía al pueblo nahua, nativo del golfo de México y al que pertenecían los mexicas (los que ahora llamamos aztecas), aunque Malinche no era de la misma etnia que los gobernantes de Tenochtitlán, lo que resultaría clave en la enemistad que sentía hacia ellos. En la batalla de Centla de 1519, Hernán Cortés, en una de sus primeras incursiones en México, derrotó a los indios chontales de Tabasco, que, entre otras cosas, entregaron a los españoles diecinueve esclavas que habían sido secuestradas de las regiones circundantes a Tabasco, entre ellas Malinche.
Inicialmente, Cortés no sintió ningún interés especial por ella, pero pronto se dio cuenta de su valor estratégico, puesto que, además del español que aprendió con sus captores, sobre todo de Jerónimo de Cozumel, Malinche hablaba maya y náhuatl (el idioma de los mexicas de Tenochtitlán), por lo que sería una intérprete perfecta para la empresa española. Además de acompañar a Cortés en sus misiones diplomáticas, asesorándolo sobre las costumbres y las estrategias militares de los mexicas, Malinche se convirtió en su amante, dándole un hijo en 1522, Martín Cortés (que fue reconocido por Cortés, aunque él y su madre no estuvieran casados). Malinche también demostró tener talento y perspicacia para aprovechar los altibajos de la política mexica, logrando dar en el punto débil de los pueblos a los que Cortés quería ir sometiendo; por ejemplo, fue ella quien avisó a Cortés de que los habitantes de Cholula pretendían rebelarse contra el yugo español, con lo que el conquistador logró aplacar, bastante violentamente, la insurrección antes de que esta ocurriera. Este empeño en ayudar a los españoles en contra de «los suyos» ha hecho que en el México moderno a Malinche se la considere a menudo una traidora a su patria, pero no hay que olvidar que en aquella época no había un país al que Malinche le pudiera guardar lealtad, y que el Imperio mexica había conquistado territorios y esclavizado pueblos como el de Malinche, por lo que las enemistades intestinas que precedían a Cortés y que animaron el comportamiento de Malinche no pueden atribuirse solamente a los españoles.
No se sabe a ciencia cierta cuándo murió Malinche, puesto que tras la toma de Tenochtitlán hay muy pocas referencias a su vida, pero su influencia en la cultura mexicana moderna es indudable: una de las principales artífices de la conquista española y una de las primeras mujeres de relevancia en la historia del México poscolombino, Malinche levanta tantas pasiones como ampollas quinientos años después de su muerte.
