The Totonacs accepted a change of religion and idols as they might have cast off an old garment and donned a new one. Like the Cozumelans and Tabascans, they were forcibly converted to the new faith. They clung to it while the Spaniards were with them, then lapsed into the worship of their ancient deities. Cortés commanded the old soldier to instruct them in the making of wax candles, to be burned before the Virgin, and after the Indians had been treated by Father Olmedo to another sermon on their duties to religion, they were allowed to retire to their huts.

Meanwhile work on the new city at the coast had been carried along with vigor, so that, while making friends and allies of the natives, Cortés had also established a base of supplies and a strong fortress as a retreat in emergency. This, the first settlement made by white men in Mexico, occupied a plain at the foot of a mountain about four leagues north of Cempoalla, and Cortés himself assisted in laying the foundations, working with his men, as he marched with them to battle, in the fore-front, encouraging them by his example.

The soldiers had seen these preparations for a fixed base in the new country, some with exultation, others in despair. They were aware, by this time, of their commander's unyielding character, and knew that, having set his face towards the object of his desires, there would be no turning back; but they did not even dream of the means he would take for preventing their departure, as Cortés took one step at a time and kept his own counsel.

The foundations of a city having been laid with due ceremony (a jail and a gallows-tree being among the first structures erected, as was the Spanish custom of those times), Cortés next turned his attention to securing favor at the Spanish court. By a vessel just arrived at the port he received information that Velasquez had obtained a warrant for colonizing new countries, over which he was to exercise the power of adelantado, or supreme governor. This was a serious thing for Cortés, as he himself desired to be made adelantado  over Mexico (when he should have conquered it), and therefore must secure the favor of his sovereign and establish direct connection with Spain instead of with Cuba and Velasquez. The manner in which he thought of doing this was by sending a vessel straight to Spain, laden with all the treasure obtained from Montezuma, together with a letter explaining the true nature and extent of his discoveries, with a request for authority to continue in his scheme of conquest.

By means of bribes and threats he induced the soldiers to part with their individual shares of Montezuma's treasure, setting the example himself by giving up the fifth which had been granted him by the council; and the whole was sent, a glorious gift, to the emperor. The best vessel of the fleet was selected, manned with fifteen sailors, and placed in charge of Puertocarrero and Montejo, with the veteran Alaminos as pilot. This vessel, the first that ever made a direct voyage between Mexico and Spain, set sail on July 26, 1519, carrying the commissioners and the Aztec treasure. A circular letter from Cortés, the council, and the common soldiers, stated what great things had been done, and the still greater yet to do, in the conquest of a vast empire, the resources of which might be inferred from the treasure remitted to his highness, as a pledge of their loyalty and devotion.

"And we further stated," says one of that intrepid band, "how we were at present 450 soldiers, surrounded by hosts of enemies, and ready to lay down our lives for the service of God and his majesty. And we supplicated that his majesty would be pleased not to bestow the government of so great and rich a country, which deserved to be ruled by a great prince or lord, on any unworthy person. In the mean time, we remained under the command of his majesty's faithful servant, Cortés, whose merits we exalted to the skies."

Cortés himself wrote and sent by the hands of Puertocarrero, the first letter of that remarkable series known as the "Cartas de Cortés,"  which historians have pronounced peerless of their kind, and which proved that their author, like the great Caesar, could handle the pen with facility, as well as the sword. The devoted craft containing this desperate venture of that little band, then cut off from all others of their race, on the coast of an unknown country, sailed on its course for Spain. Contrary to orders, she touched in at a port on the north coast of Cuba, whence the tidings were carried to Velasquez by a sailor who deserted the ship. The governor sent a war-ship to intercept her without delay, but she evaded capture, and after a voyage considered short and prosperous for those days, arrived safely at San Lucar in October.

A few days after the sailing of the ship for Spain, some soldiers and sailors, friends of Velasquez, seized a ship in port, intending to hasten to Cuba and beg the governor's assistance. Their conspiracy was betrayed to Cortés, who, acting with his customary promptness, sentenced the ringleaders to death, cut off both feet of the pilot, and gave the rest one hundred lashes each, sparing only one, a priest. Among those who were executed was the very man who, in his capacity of alguacil, had arrested Cortés in Cuba when trying to escape the clutches of Velasquez.

Stern Cortés urged swift judgment upon the rebels; but, says an eye-witness of the occurrences, he sighed deeply when he came to ratify their sentence, exclaiming, "How happy is he who is not able to write, and is thereby prevented from signing the death-warrants of his fellow-men!"

This attempt at desertion, so nearly successful, caused Cortés to determine upon the removal of such a menace to his success and safety as a fleet in his rear, while he himself might be hundreds of miles distant from his coastal base, and in the midst of enemies. After the pretence of a survey by a board of officers, he gave orders for the entire squadron to be sunk at its moorings. The vessels were dismantled, all their removable equipment taken on shore, and then, with the sole exception of one small craft, they were scuttled. Thus all means of present escape from the country were removed, whether of friends of Velasquez or Cortés.

Both soldiers and sailors were appalled at this desperate act. Murmurs arose that were only hushed when their great leader appealed to their pride of race, to their sense of justice, even remarking that he himself was the greatest sufferer, as two-thirds of the fleet belonged to him, and by destroying the ships he had sacrificed all his worldly possessions. It would seem, he said, like distrusting the valor of the Spanish soldier to assert that, now all means of retreat were cut off, his followers must either conquer or die; but their reason would convince them that by releasing 100 sailors the force of fighting men was greatly strengthened.

A valiant veteran, Juan de Escalante, was left in charge of Villa Rica, with a command composed chiefly of the disabled men of the army and navy. He was commended to the protection of Cempoalla's cacique, who furnished Cortés with 2000 men as carriers, together with 200 more to draw the cannon. A definite departure from the coast was made on August 16, 1519, and the long journey to Anahuac was at last begun.

Six months had passed since that gallant company set sail from Santiago, two-thirds of the time having been taken up in fruitless negotiations and contentions among themselves. But in the end the inflexible Cortés had triumphed, and he now had the satisfaction of setting out in earnest for the Aztec capital, to which he had not been invited, but from which, in truth, he had been warned away.

Little reeked stout Cortés that the great Montezuma had denied him hospitality. He had a message to deliver, a cause to advance. He was now rejoicing at the end of inaction and nursing hopeful anticipations of ultimate triumphs. Some of his soldiers may have shared their commander's sentiments; at all events they were overcome by his forceful arguments, supported as they were by the civil and military authority with which they themselves had clothed him. At first stupefied at the loss of their ships—their only means of escape from the country—then sullenly yielding consent to their leader's schemes, finally they thrilled with the enthusiasm born of high emprise, and shouted, "On to Mexico!"

Those valiant captains, Sandoval and Alvarado, had made forays into all the region roundabout Totonac territory, compelling the people to acknowledge Spanish supremacy, so Cortés left no foes behind to "kindle a fire in the rear," and the invaders marched forward with confidence, though compelled to subsist upon the country as they went along. Passing through the tierra caliente, with its wonderful forms of tropical vegetation, the Spaniards next entered a region lying at a higher altitude, where the signs of exuberant fertility and the softness of the airs made a visible impression upon their spirits. Finding peace and contentment everywhere, and relieved of their burdens by the 2000 Indian carriers, the soldiers swung merrily along, by nightfall of the first day reaching the aboriginal city of Jalapa.

Jalapa is situated at a height of about 4000 feet above the level of the sea, amid scenery of surpassing beauty. Grander and wide-spread became the views as the invaders climbed the slopes of the eastern cordilleras. Great mountains and deep barrancas  opened to their view, above all rising splen did Orizaba, the Aztec Ciltlaltepetl, or "Mountain of the Star," whose shining, snow-covered peak had greeted them through the mists of the gulf as they approached the coast at Vera Cruz. The heated coast region was now far below them, and they were traversing the verdant vales and oak-crowned hills of Mexico's second climatic zone, the templado, or temperate region. Beyond that they encountered the keen, searching winds of the tierra fria, the zone of cold, where their Indians of the hot country, especially those from torrid Cuba, suffered terribly from exposure, some of them falling before the blasts and dying in their tracks.

When well into the tierra fria, they came to a place called Xocotla, containing thirteen temples and other large stone structures. Here they received definite information as to "what sort of a person the great Montezuma was "of whom they had heard so much. He was the most powerful monarch in the world, said the cacique of Xocotla province, who told them further that the renowned city of Mexico, Aztlan, was built upon an island in a lake, which was the centre of a vast and beautiful valley. This city was accessible only by canoes, or by four great causeways of stone several miles in length, in which were wooden bridges that could be raised, thus cutting off communication with the mainland, as many Spaniards afterwards found at the cost of their lives on the night of their retreat from the Mexican city in the lake.

In response to a demand that Cortés made for gold to send to his sovereign beyond the sea, the cacique answered, tauntingly: "Gold? Yea, have I gold enough; but I cannot give it without the orders of Montezuma, my king. Though if he orders me, I will render up not only that, but all my estate, even my life itself!"

"Sayest thou so?" rejoined Cortés. "Then will I soon make him order you to give it me, and all that you have. Moreover, I shall require you and all others to renounce your human sacrifices, cannibal feasts, and other abominable practices; for such is the command of our Lord God, whom we adore and believe, and who, at the last, is to raise us up in heaven." He was moved to these remarks by what he had seen in one of the temple courts, where were thousands of human skulls heaped up in front of the idols.

The Spaniards were surely in no condition to enforce any demands they might make, being greatly fatigued and wellnigh famished. Cortés, also, was called upon at Xocotla to decide between two routes leading thence to Mexico, one being by way of Cholula and through territory entirely controlled by the Aztecs; the other via Tlascala, a small republic, which for many years had maintained successful opposition to the Mexicans. The Cholulans were the milder people, he was told, but treacherous and in the pay of Montezuma; while the Tlascalans, though valiant and warlike, were at peace with the Totonacs, who strongly advised Cortés to pass through their territory.

Acting upon their advice, Cortés sent a letter, in which he informed the Tlascalans that he was on his way to Mexico and desired safe conduct through their republic, adding that he had freed the Totonacs from the yoke of Mexico and might also be of service to them in their wars. It was a crafty message, with but one defect: it was written in Spanish, a language which, of course, the Tlascalans did not understand. This did not matter in the eyes of Cortés, who sent the letter by the hands of four Cempoallans, together with gifts: a crimson cap, a sword, and a cross-bow.

There was no mistaking either the purport of the letter or the meaning of the gifts, as one of the Cempoallans, when arrived at the capital of Tiascala, addressed the senate, the governing body of the republic, saying: "Most great and valiant chiefs, may the gods prosper you and grant victories over your enemies. The lord of Cempoalla, and all the tribes of the Totonacs, desire to acquaint you that from the East, from the direction of the great sea, have arrived in large ships, on the coasts of our country, certain bold and adventurous men, by the assistance of whom we have been freed from the tyrannical dominion of the Mexican king."

This was the speech (errors arising from mistakes made by the historians aside) as reported by one of the company so anxiously awaiting the Tlascalans' response. The four lords, chiefs, or caciques who composed the government, after long deliberation, declared in favor of admitting the strangers within their walls; but a son of one of these lords, young Xicotencatl, who was also commander-in-chief of the armies, recommended caution. Lord Maxicatzin, one of the nobles, having suggested the possibility of these men being messengers from Quetzalcoatl, Chief scornfully replied: "Say, rather, they are monsters cast up from the sea because it could not endure them in its waters . . . . These are not gods who so greedily covet gold and carnal pleasures; and he wrongs the honor of this republic who says it can be overcome by a mere handful of base adventurers. . . . Let me have my way with them first. If they are mortal, the arms of the Tlascalans will proclaim it all around; and if immortal, there will yet be time to allay their anger by homage and implore their mercy!"