Early in life he had developed that spirit of daring and courageous persistence in his undertakings which was to mark his whole career. As a young man, he had acquired a skill and a reputation for seamanship. His early fame in that regard was to enhance all his later undertakings.

Menéndez was a careful planner, a prudent and capable administrator. He was also a born diplomat, wise in ways of avoiding the pitfalls so common in diplomacy. He was not above a certain degree of chicanery, while at the same time he must be credited with adhering to what he perceived to be true and worthy. If his memory is besmirched in history by acts of cruelty in summarily dealing with those he regarded as enemies, it can only be said that in this he shared the spirit of most of his adversaries, as also he shared several other weaknesses common to his time.

Persuaded of Menéndez' ability as a seaman, on March 20, 1565, Felipe II issued an asiento authorizing him to undertake an expedition for gaining the definitive control of La Florida, already claimed by the Spanish Crown for some four decades. It was a claim increasingly contested by other European states, especially France. The exploration of La Florida, its conquest, and its settlement were the stated objectives of the mandate issued in favor of Menéndez. Another purpose also to be promoted at the same time, and no less fervently, was the conversion to the Catholic Faith of the natives who inhabited the territory. Indeed, the converting and civilizing of the natives was seen as a definite move to strengthen Spain's title to the territory.

The French, chief rivals of Spain in international policy, having already penetrated the land, were intent on fortifying their hold on it. They were, in addition, ardent promoters of the sect known as the Huguenots and virulent persecutors of Catholics. It was part of French strategy in La Florida to attract the natives to adhere to the French Huguenots. Menéndez was charged to rid the land of the heretics, thus the more certainly to assure Spanish possession of La Florida.

To realize this objective – in the asiento authorizing Menéndez to undertake the expedition it was, as a matter of fact, the first to be stipulated – the adelantado was to have a minimum of ten members of some religious order of men which he might choose, and, in addition, four members of the then-recently founded and approved Society of Jesus. It was the very first foreign mission assumed by the Jesuits. The special designation of the Jesuits for this mission was due, at least in part, to the regional linkage of the Asturian adelantado and the heavily Basque background of the Jesuit movement in its early days. It is not without significance that Ignacio de Loyola, the founder of the Society, was a fellow-Asturian, and that Duke Francisco de Borja, his successor as General Superior of the young Society, was likewise a Basque. Under such inspiration and guidance, it must have been reasoned, the zealous members of the military-like Society of Jesus would be ideal agents for the challenges to be anticipated in dealing with the Indians of distant Florida. Meanwhile, the provision to introduce another religious order into the project remained in abeyance.

Reliable reports of French and English designs on the region gave urgency to the departure of the Menéndez expedition. It was confirmed that the French – Huguenots, or (as more commonly designated) Lutherans – were readying a massive expedition to sail for La Florida: its purpose none other than to assure for France the control of the sea-lanes between the many Spanish colonies in the New World and the ports of Europe. The Bermuda Channel, sweeping by the territory of La Florida and known to the Spaniards as la Carrera de las Indias, was vital to Spain's continued prosperity.

Urgently important was it, therefore, that Spain should enter decisively into the territory claimed in her name more than half a century earlier. The pressure for the definitive possession and control of La Florida, as opposed to a merely theoretical one, explains the haste with which the Menéndez expedition was organized following the issuance of the asiento in March of 1565. The myriad preparations for the sailing having been made, the fleet of Menéndez de Avilés left Cadiz on June 29 of that year, 1565. In mid-ocean the flotilla ran into violent storms and hurricanes. Of the nineteen vessels that formed the convoy as it departed from Cadiz, no more than six had reached San Juan de Puerto Rico by the time determined by the adelantado for continuing on to La Florida. The prominence given in the asiento to evangelizing the natives did not deny the importance of two other motives for the undertaking committed to Menéndez. He was to settle loyal Spaniards on the land which, for so long a time, had been claimed by Spain by reason of the discovery made by Ponce de León in the year 1513; and he was to dislodge those unauthorized intruders reported to have invaded and established themselves on the coast near where the River of May (St. Johns) emptied into the sea. If the expedition was primarily a military undertaking, at the same time it was the fulfillment of a long-held plan to colonize the area of La Florida. And the work of evangelizing the natives was an integral part of the plan.