Mormonların bölgeye ilk gelişlerinin öncesinde, Utah’ta Amerikalı yerli kabileleri yaşamaktaydı. Bu kabilelerden birisi eyaletin doğu kesiminde toprakların yarıdan fazlasını kaplayan ve eyalete ismini veren Ute kabilesiydi. Diğerleri ise, batı çöllerinde yaşayan Goshute ile güneybatı tarafında bulunan Southern Paiute kabileleriydi.

Utah’a gelen ilk yabancılar, 18. yüzyıl başlarında bölgeye ilerleyen Meksikalılar ve İspanyollar olmuştur. Juan María Antonio Rivera’nın bugünkü Moab yakınlarından eyalete ulaştığı bilinmektedir. 1776 yılında iki Fransiskan rahibin önderliğindeki grup ise Utah’a doğudan giriş yapmıştır. 1840’larda Utah, Kaliforniya’ya geçişler için sıklıkla kullanılmaya başlanmıştır.

1847 yılında ilk Mormonlar bölgeye yerleşmeye başlamışlardır. Mormonlar doğal kaynakları topluluğun malı, kiliseyi de ilk hükümet olarak kabul etmişlerdir. Yerleşimin kısa bir süre sonrasında yerlilerle savaşlar başlamıştır. Yapılan iki savaşın (Walker Savaşı, 1853-1854 ve Balck Hawk Savaşı, 1865-1868) ardından yerliler bölgeden uzaklaştırılmışlardır.

Guadalupe-Hidalgo Anlaşması’nın (1848) güneybatının çoğunu Birleşik Devletler olarak tanımlamasının ardından Mormonlar Deseret eyaletini kurmuştur. Ancak, bu eyalet kongre tarafından birliğe alınmamıştır ve bunun yerine Utah Territory (Utah ile Nevada ve Wyoming’in bazı kısımları) oluşturulmuştur.

1870’lere kadar Utah’ın toplam nüfusunun neredeyse yüzde 98’i Mormonlardan oluşmaktaydı; politikada, ekonomide ve sosyal hayatta Mormonların sözü geçiyordu. Ancak Bingham Canyon’da gümüş bulunmasıyla çoğunluğu Mormon olmayan madenciler bölgedeki politik ve sosyal hayatta etkin hale geldi. 1891 yılında cumhuriyetçi ve demokrat partiler kurularak dine dayalı politik ayrıma son verilmiştir ve Utah 4 Ocak 1896 tarihinde eyalet haline gelmiştir.