During his years in Mexico, de Luna had served with Francisco Vásquez de Coronado on his expedition to the Seven Cities of Cíbola and crushed an Indian rebellion in Oaxaca. De Luna was chosen by Luis de Velasco, Viceroy of New Spain (Mexico), to establish a settlement on the Gulf Coast of what is now the United States, and clear an overland trade route to Santa Elena (on Tybee Island, Georgia), where another outpost would be founded. A site named "Filipina Bay" had been recommended from the September 1558 voyage of Guido de las Bazares. De Luna was given thirteen ships and more than 1,500 soldiers and settlers, under six captains of cavalry and six of infantry. De Luna, however, proved an incompetent leader, and the expedition was plagued by disaster.

The party anchored in Pensacola Bay (which they called "Ochuse") and set up the encampment of Puerto de Santa Maria during the summer of 1559, at the site of the modern Naval Air Station Pensacola. De Luna dispatched the factor Luis Daza with a galleon back to Vera Cruz to announce his safe arrival. He fitted two other vessels to sail to Spain, awaiting the return of two exploring parties. With much of the colony's stores still on the ships, de Luna sent several exploring parties inland to scout the area; they returned after three weeks having found only one Indian town. Before they could unload the vessels, on the night of September 19, 1559, a hurricane (with storm surge) swept through and destroyed most of the ships and cargo: five ships, a galleon and a bark, pushing one caravel and its cargo into a grove inland. With the colony in serious danger, most of the men traveled up the Alabama River to the village of Nanipacana (Nanipacna or Ninicapua), which they had found abandoned; they renamed the town "Santa Cruz" and moved in for several months. Back in Mexico, the Viceroy sent two relief ships in November, promising additional aid in the spring.

The relief got the colony through the winter, but the supplies expected in the spring had not arrived by September. De Luna ordered the remainder of his force to march to the large native town of Coca, but the men mutinied. Bloodshed was averted by the settlement's missionaries, but soon after, Ángel de Villafañe arrived in Pensacola Bay and offered to take all who wished to leave on an expedition to Cuba and Santa Elena. De Luna relented and agreed to leave, eventually moving back to Mexico, where he died in 1571. The Pensacola colony was inhabited for several more months by Captain Biedma and a detachment of fifty men who Villafañe had left there, in case further orders arrived from Viceroy Velasco; when they sailed away, the area was not populated again by Europeans until 1698, when the Spanish founded the city of Pensacola.