The first tourists to visit Odessa 446 years ago were three adventurous Spanish Conquistadors and a Black man from the Mediterranean.

Alvar Nunez (Cabeza de Vaca) and his companions,CapitanAlonso del Castillo Maldonado, Capitan Andres Dorantes de Carranza and Estevanico (Dorantes' Black Moorish slave) trekked westward across the continent from Galveston Island where they had been shipwrecked. During this 1534-36 journey, they passed the Liano Estacado, just south of Odessa.

They chose the inland route because the native inhabitants treated them better than the Island Indians and other hostile Texas tribes. These men had great faith in their Christian God and were able to effect miraculous cures among several tribes of Indians they encountered in this area. Great numbers of the awed natives followed the explorers and their fame spread from tribe to tribe by drum beats and smoke signals.

The ancient Jumanos tribe inhabiting this area were described by Cabeza de Vaca as the "striped tribe" who were naked. This old tribe was eventually absorbed into the Apache tribe and Mexican race. Their small, finely-chipped arrowheads with sharp tips and long stems have been found in abundance throughout area sandhills.

In 1650, the Governor of New Mexico, General Hernando de la Concha, sent Capitan Herman Martin and Capitan Diego del Castillo from Santa Fe to explore Texas as far as the "Rio de los Nueces" (present day Concho River). Their route brought them northeast of Odessa. They returned over virtually the same ground with fresh-water pearls, found in the Concho.

Four years later, Sergeant Major Diego de Guadalajara set out with 30 soldiers and some 200 Christian Indians. They followed the same route staked by Martin and Castillo and made good use of water holes left by recent rains on the Llano Estacado. Juan Dominguez de Mendosa, then twenty-three years old, was a member of the expedition.

By the year 1680, Mendosa had risen in rank to Lieutenant General and Maestro de Campo of New Mexico. He embarked on another mission that came through Odessa and was joined along the way by a Spanish Padre, Father Fray Nicolas Lopez. Together, they taught Christianity to the Indians and obeyed an order to "bring back another load of pearls" from Texas rivers.

In 1761, Felipe de Rabago y Teran blazed a trail from Mission San Saba (present day Menard, Texas) to New Mexico. There were 40 men in his party. The group went from the headwaters of the Concho River overland to the Pecos River. They were the first travelers on record to have traversed the route that is now U.S. Highway 80 and the first to tread the soil of what was to be downtown Odessa.