An exploring party from the expedition of Francisco Coronado may have entered the region as early as the mid-16th century, but the first major exploration did not take place until 1776. That year two Franciscan friars, Silvestre Vélez de Escalante and Francisco Domínguez, led an expedition into Utah. They were seeking a direct route from Sante Fe, New Mexico, to Monterey, California, and their efforts resulted in the establishment of trade routes between New Mexico, Utah, and California. The Spanish and later the Mexicans claimed the territory that became Utah, but neither ever exercised actual control.

During the late 1700's and early 1800's, Utah was visited by more explorers, by settlers on their way west, and by British and American fur traders and trappers. The trappers, also called mountain men, included Peter Skene Ogden of the Hudson's Bay Company; Jim Bridger, Jedediah Smith, and William H. Ashley, representing the Rocky Mountain Fur Company; and Etienne Provost, Antoine Robidou, and Kit Carson. During the winter of 1824–25, Bridger and Provost independently discovered the Great Salt Lake.

Several trading posts were established in Utah in the 1830's and 1840's. Fort Kit Carson (1833), Fort Davy Crockett (1837), Fort Robidou (1837), and Fort Bridger (1843) were built in the eastern mountains of Utah. Fort Buenaventura was set up by Miles Goodyear near present-day Ogden in 1846. These posts all were eventually abandoned or were destroyed by Indians. A major scientific exploration of Utah for the United States government was undertaken by John C. Frémont, 1843–45, even though the territory was still part of Mexico. His detailed reports sparked interest in the region and the maps he prepared were later used by pioneers traveling to the Far West.