Cortés initially arrived on the Yucatán peninsula in the southern part of Mexico. Most of the indigenous people he encountered resisted his pleas for peace and attacked the Spaniards with all of their forces, without much success. In the early struggles, the Spaniards prevailed because of their weapons and their ability to fire on the enemy from horseback. As they gradually fought their way up the coast and won victories over the indigenous populations, he learned that the great wealth of the country lay in its interior, in what was called Mexico [Tenochtitlan]. Though he made peace with the vanquished, Cortés never knew whom to trust.

As he reached the Totanac city of Cempoala, citizens greeted the Spaniards enthusiastically and told Cortés that "The Fat Cacique" was too heavy to come with the party, but he described Tenochtitlan, complained of the Mexicas, and suggested an alliance.

While the Spaniards were in Cempoala, the Mexicas sent tax collectors and warned the Cempoalans against receiving the strangers. Cortés could see there was a problem, but Malinche figured it out right away, allowing Cortés to solve it by promising to protect the Cempoalans, many of whom accompanied him as he marched toward Tenochtitlan. At the same time, he released the Mexica tax collectors, telling them that he hoped the emperor was well and that he wished to meet him. He unselfconsciously intended to play both sides against the other until he could determine whom to trust.

Before moving inland, Cortés founded a city and fortress called Vera Cruz or Villa Rica that he left in the command of Gonzalo de Sandoval, frequently identified in the sources as the alaguacil mayor or sheriff, and sunk his ships to avoid mutiny. Fearless, he began his expedition inland toward Tenochtitlan.

As he marched inland, Cortés received friendly messengers and gifts of gold from Moctezuma, which only served to induce the suspicion of the Tlaxcalans, fierce enemies of the Mexicas. The Tlaxcalans refused to greet Cortés and fought against him. The Tlaxcalans, probably like other warriors, determined that the horses gave the Spaniards a decisive advantage and killed two of them.

The Tlaxcalans themselves were divided between followers of Xicotencatl the Elder, who saw the Spaniards as a potential ally, and his son, Xicotencatl, the Younger, who was adamantly opposed to the Spanish invasion. Ultimately, after losing many warriors to the superiority of Spanish weapons, Xicotencatl the elder prevailed, the son was executed for treason, and the Tlaxcalans became the Spaniards' best and most loyal allies.

Xicotencatl, despising the Mexicas and their allies from the city of Cholula, did everything he could to persuade Cortés to attack that city. Cortés still not sure who to trust proceeded with caution delighted that their was no unanimity among the indigenous peoples he encountered. He thus proceeded towards Cholula, initially seeking an alliance.

With large numbers of Cempoalans and Tlaxcalans, mostly carrying the baggage and weapons but many armed as well, Cortés reached the countryside outside Cholula. The Cholulans initially received him warmly, although they refused to allow the Tlaxcalans into their city. Cortés complied and told the Tlaxcalans to camp in the countryside, hoping to make peace with the Cholulans.

It is not entirely clear what happened next. The Mexicas claimed the Spanish simply massacred them.. Both Cortés and Díaz del Castillo agree that they were warned about Cholulan and Mexica plans to trap the Spaniards inside the city to slaughter them. A Tlaxcalan account written at least fifty years after the event made a similar argument. The major image of the event, also from a Tlaxcalan perspective, suggests that the Cholulans committed suicide because their gods failed them, an argument also made by Cortés. In any case, Cortés planned to attack them before they could attack the Spaniards and gave the signal for everyone, including the Tlaxcalans, to attack.

Seeing the viciousness of the Tlaxcalan attack, Cortés called it off and sent the Tlaxcalans back to their camp under Spanish supervision. Many descendants of the Mexicas believe the Spaniards simply slaughtered innocent people without provocation.

Cortés agreed to spare the survivors and urged the Cholulans to restore their markets and fairs. He tried to convert them without much success and proceeded through the mountains toward Tenochtitlan. The Spaniards sent messengers to Moctezuma asking for peace and a meeting. Moctezuma insisted that the Spaniards stay where they were, claiming there were not enough resources to support them in the interior (which was probably true).

There were two roads from Cholula toward Tenochtitlan. The Mexicas advised the Spaniards to take one road and basically blocked the other. Cortés, believing that the Mexicas had blocked the road to persuade them to take the other road, where they would be trapped, decided to take the blocked road.