Aunque Cristóbal Colón nunca llegó a pisar territorio mexicano, sí tenía conocimiento de una región llamada Maya al oeste de las Indias. El primero en interesarse directamente por estas tierras fue Diego Velázquez, el Adelantado de Cuba, quien quiso viajar hacia el occidente con el fin de buscar un paso hacia Asia. En 1517 mandó una expedición a la península de Yucatán, pero tras haber sido recibida en paz, su tripulación fue emboscada y terminó por huir. El año siguiente zarpó una segunda expedición que llegó al territorio del actual Tabasco y Veracruz. Fue aquí donde los españoles supieron de la existencia de los mexicas, quienes ejercían el control sobre la región.

En 1519 salió la tercera expedición con 508 soldados, 100 marineros y 17 caballos bajo el mando de Hernán Cortés. Tras desembarcar en la isla de Cozumel, Cortés pagó el rescate de Jerónimo de Aguilar, quien había naufragado en la zona ocho años atrás y posteriormente fue capturado por los mayas. Debido a que este conocía la lengua y las costumbres del imperio, le servía a Cortés como intérprete. En Tabasco, los españoles derrotaron a los habitantes de la zona, y recibieron veinte esclavas como ofrenda de paz, entre ellas Malinche - la famosa intérprete, consejera y compañera de Cortés (Malinche conocía tanto el idioma maya como el náhuatl, y Jerónimo de Aguilar sabía traducir del castellano al maya).

Al llegar los españoles a la costa de Veracruz, los mexicas se acercaron a las embarcaciones, convencidos de que se trataba de la llegada de sus dioses. Aquí los dos bandos intercambiaron regalos de gran valor, enviados por el líder del imperio mexica, el huey tlatoani Moctezuma. Cortés, por su parte, no tardó en organizar un desfile militar en la playa para intimidar a los mexicas y alimentar su creencia de que sus fuerzas eran de naturaleza divina. Enseguida salieron mensajeros a Tenochtitlan para informar al emperador de los sucesos. Moctezuma quedó tan impresionado como atemorizado, y envió nuevamente regalos, pidiéndoles a los españoles que se marcharan. Estos hicieron caso omiso y, motivados por la riqueza del imperio, decidieron avanzar hacia el interior. 

En el camino, los conquistadores llegaron a acuerdos con diferentes pueblos sometidos por el imperio mexica, notablemente con los totonacas y los tlaxcaltecas. Estos combatirían como aliados junto a los españoles, negándose a aceptar las condiciones de opresión bajo las que vivían. 

Antes de llegar a Tenochtitlan, los españoles, totonacas y tlaxcaltecas entraron en Cholula, una ciudad de treinta mil habitantes. Al inicio, los recién llegados recibieron un trato principalmente hospitalario, sin embargo, los cholultecas cambiaron de postura al cabo de unos días. Bajo este contexto, una anciana le reveló a Malinche que las autoridades cholultecas habían recibido una orden de emboscar y aniquilar a los españoles, noticia que esta transmitió a Cortés inmediatamente. Al día siguiente, Cortés capturó a los líderes cholultecas e inició un ataque supuestamente preventivo contra los lugareños. En tan solo un par de horas murieron más de cinco mil cholultecas, muchos de ellos civiles, y la ciudad fue incendiada y saqueada. Los sobrevivientes terminaron por aliarse a los españoles, quienes siguieron su camino a Tenochtitlan dos semanas después.