For months the Spaniards lived and moved freely about Tenochtitlan, as Cortés essentially ruled through Moctezuma. Though there were many tensions, everything seemed to be under control. Events started to unravel in April 1520, when Cortés learned that the Governor of Cuba, Diego Velásquez and Cortés immediate superior, had sent a force of over a thousand soldiers with artillery to capture and imprison the Spanish conqueror. Under command of Pánfilio Narváez, the force began to take over Vera Cruz, and when the indigenous people learned that Narváez and the King thought Cortés was a traitor, they began to revolt.

There is considerable evidence that Narváez deliberately said evil things about Cortés in order to instill rebellion, and Moctezuma regained a new hope that he might be able to get rid of the Spaniards. As Cortés had done earlier, he played the two sides against each other, a fact which would later enrage Cortés.

Recognizing that he had only a few hundred men to fight as many as a thousand well-armed soldiers, Cortés was deeply concerned. His first response was to send messengers with gifts of gold, who explained that he was in control of a very wealthy city because its inhabitants thought he was a god. He added that there was no need to fight each other, as there was plenty of gold for everyone. But Narváez, recognizing that he greatly outnumbered Cortés, apparently believed he could acquire Mexico for himself or, at least, that is what Cortés thought.

When Cortés realized that Narváez was not going to cooperate, he determined that he had to capture Narváez if he wanted to preserve his grand plan to keep Mexico under his control. He thus set off with the few hundred men he had, leaving Tenochtitlan in the hands of Pedro de Alvarado and a handful of soldiers.

After giving a rousing speech to his soldiers and marching rapidly, Cortés arrived outside Cempoala secretly in the night and attacked suddenly during a rainstorm. He did not entirely surprise Narváez's soldiers, but there was a lot of confusion. Cortés' men fought their way up the stairs of a tower where Narváez was headquartered. Cortés soldiers would gain and lose stairs, but suddenly Narváez cried out that he was dead [he wasn't], but he did lose an eye in the struggle.

Cortés imprisoned him and pacified many of his soldiers by promising them gold if they would join him, as most did. He regained control over the indigenous people and found that he had gained a great deal in terms of men, weapons, and horses from his victory.

While in Cempoala, he received an urgent message that things were falling apart in Tenochtitlan that the Mexicas had besieged the Spaniards in their quarters, that many had died and all were starving without access to food or water.

Thinking that once he returned, he would be able to calm the population, he marched with his new army to Tenochtitlan at once.