Before proceeding on his march to Mexico, Cortes destroyed all his ships, lest his men might mutiny, as they seemed disposed; and leaving 150 Spaniards in Vera Cruz, with as many Indians to serve them, he began his march.  Going first to Zempoallan, he learnt that Francis Garay was on the coast with four ships, and he contrived to inveigle nine of his men, from whom he understood that Garay, who had been in Florida, was now at the river Panuco, where he had got some gold, and meant to remain and build a town, now called Almeria.  Cortes destroyed the idols of Zempoallan, and overthrew the tombs of their kings, whom the people worshipped as gods, and exhorted them to worship the true God.  He set out from Zempoallan for Mexico on the 16th of August 1519, and after three days march came to the city of Zalapan, and thence to another named Sicuchimatl; at both of which places he was well received, and was offered to be conducted to Mexico, such being the orders of Mutecuma.  Going from thence he ascended a hill three leagues high, on which vines were seen growing; and in another place he saw above a thousand load of wood ready cut.  Beyond this he passed a plain country, which he named Nombre de Dios.  At the foot of this mountain, he rested his troops at a place called Teuhixuacan; whence, through a desert country, he came to another mountain, which was covered with snow and excessively cold, and where the troops rested in a town named Zacotlan.  Marching thus from town to town, he arrived at a territory called Tlaxcallan, which was at war with Mutecuma; and as the people were valiant, they fought against Cortes; but at length they agreed, and formed a league with him against the Mexicans.

Thus, from country to country, he came at length within sight of Mexico; and Mutecuma, being afraid, received him kindly, giving him and all his people lodgings in the capital, and all things necessary.  After a time, fearing to be slain, Cortes made Mutecuma prisoner, and brought him to his own quarters, keeping him under a secure guard.  Cortes inquired at Mutecuma the extent of his dominions, where the mines of gold and silver were, and the number of kings who dwelt in the land.  And joining eight intelligent Spaniards with an equal number of Indians, he sent them, in four companies, to travel into four separate countries, Zucolla, Malinaltepec, Tenich, and Tututepec.  The messengers to Zucolla had 80 leagues to travel, and those who went to Malinaltepec 70; both of which provinces were under subjection to Mutecuma:  they found both of these countries fertile and well peopled, and they brought back samples of gold, which the natives found in the rivers.  The country of Tenich was at war with Mutecuma, and would not admit the Mexicans into their country; but they sent ambassadors to Cortes with presents, offering him their amity, at which Mutecuma was much displeased.  Those who went to Tututepec, near the South Sea, brought back samples of gold, and praised the pleasantness of the country; reporting that there were many good harbours on the coast, and they presented to Cortes a beautiful cloth of cotton, on which the coast, with all its harbours and creeks, was distinctly represented.  But at this time, by the coming of Pamphilus de Narvaez, the whole kingdom of Mexico was thrown into confusion.