Los Paiutes tienen su origen en la historia de Tabuts, el lobo sabio que decidió tallar a muchas personas diferentes con palos. Su plan era dispersarlos uniformemente por la tierra para que todos tuvieran un buen lugar para vivir, pero Tabuts tenía un hermano menor travieso, Shinangwav el coyote. Shinangway abrió el saco y la gente cayó en manadas por todo el mundo. La gente estaba enojada con este tratamiento, y es por eso que otras personas siempre luchan. La gente que quedaba en el saco eran los Paiutes del Sur. Tabuts los bendijo y los puso en el mejor lugar.
Los estudiosos sugieren que los Paiutes del Sur y otros pueblos de habla numica comenzaron a moverse hacia la Gran Cuenca y la Meseta de Colorado alrededor del año 1000 d.C. Antes del contacto con los europeos, la tierra natal de los Paiutes abarcaba más de treinta millones de acres del actual sur de California, el sur de Nevada, el centro-sur de Utah y el norte de Arizona. Su estilo de vida incluía mudarse con frecuencia, principalmente de acuerdo con las estaciones y las cosechas de plantas y los patrones de migración de animales, y vivían en grupos independientes de tres a cinco hogares. Las principales decisiones se tomaron en las reuniones del consejo. El líder tradicional Paiute, llamado niave, ofreció consejos y sugerencias en las reuniones del consejo y más tarde trabajaría para llevar a cabo las decisiones del consejo.
El asentamiento español en el suroeste de Estados Unidos trajo disturbios y violencia a los Paiutes del Sur. Lo más importante, los españoles introdujeron el violento comercio de esclavos a los indios de la Gran Cuenca. Debido a que los Paiutes no adoptaron el caballo como medio de transporte, sus comunidades fueron frecuentemente asaltadas en busca de esclavos por tribus ecuestres vecinas, Nuevos mexicanos y, eventualmente, estadounidenses. El tráfico de esclavos de Paiutes aumentó después de la apertura del Old Spanish Trail, una ruta comercial que conectaba Nuevo México con el Océano Pacífico. La demanda era mayor para los niños, especialmente las niñas.
Aunque a mediados de la década de 1800, los Paiutes del Sur se habían encontrado con comerciantes, viajeros y tramperos euroamericanos, pero no habían tenido que lidiar con asentamientos blancos en sus tierras. En 1851, sin embargo, los miembros de la Iglesia SUD comenzaron los esfuerzos de colonización en el área del sur de Utah, y a finales de 1858, los mormones habían establecido once asentamientos en el sur del territorio Paiute. Inicialmente, los Paiutes dieron la bienvenida a la presencia mormona, ya que les ofrecía cierta protección contra el asalto de Utes, Navajos y mexicanos. Desafortunadamente, los asentamientos mormones también trajeron epidemias generalizadas. En la década siguiente al asentamiento, algunos grupos de Paiute perdieron más del noventa por ciento de su población a causa de enfermedades. Finalmente, el gran número de colonos mormones también llevó a la competencia por las tierras y los recursos de los Paiute.
Uno de los eventos más controvertidos que involucraron a los Paiutes del Sur ocurrió en septiembre de 1857 cerca de lo que hoy es Cedar City, Utah. En la masacre de Mountain Meadows, más de cien emigrantes con destino a California fueron atacados y asesinados. Durante más de un siglo, la historia común fue que los indios Paiute atacaron por primera vez la caravana de carretas. Los Paiutes supuestamente apelaron a los colonos SUD en busca de ayuda, y los colonos se acercaron a los emigrantes bajo una bandera de tregua. Después de convencer a los emigrantes de que renunciaran a sus armas, los colonos llevaron la caravana a un lugar aislado donde posteriormente mataron a la mayoría de los emigrantes. Una vez más, los mormones afirmaron que los indios Paiute participaron en la traición, y durante años los Paiute cargaron con la mayor parte de la culpa de este trágico evento. Si bien muchos aspectos de la masacre aún están envueltos en misterio, es importante destacar que la tradición oral de los Paiute indica fuertemente que los Paiute no participaron en el ataque inicial ni en la masacre siguiente.
La primera reserva Paiute se estableció en 1891 en el río Santa Clara al oeste de San Jorge. La reserva fue reconocida formalmente por el gobierno en 1903. En 1916, el presidente Woodrow Wilson emitió una orden que amplió el tamaño de la reserva a sus actuales 26,880 acres. Pronto siguieron otras tres reservas Paiute. Las reservas resultaron ser demasiado pequeñas y carentes de recursos para que los Paiutes se mantuvieran, y los Paiutes a menudo dependían de la caridad mormona y de la buena voluntad del gobierno federal.Esa buena voluntad terminó abruptamente en la década de 1950 bajo la política de terminación del gobierno federal, que tenía la intención de imponer la asimilación y alentar la autosuficiencia entre las tribus indias, pero en cambio tuvo consecuencias sociales y económicas devastadoras. Antes de 1954, cada banda Paiute, excepto la Banda de Cedro, tenía su propia reserva y gobierno tribal en funcionamiento. Sin embargo, en caso de terminación, estas bandas perdieron el reconocimiento federal y, por lo tanto, su elegibilidad para el apoyo federal. Muchos informes indican que la tribu Paiute no estaba preparada para la terminación, y todavía es un misterio por qué fueron seleccionados para ser parte del programa. Los Paiutes sufrieron inmensamente bajo la terminación. Casi la mitad de todos los miembros de la tribu murieron entre 1954 y 1980, en gran parte debido a la falta de recursos básicos de salud. Sin ingresos adecuados para satisfacer sus necesidades, los Paiutes no podían pagar impuestos a la propiedad y perdieron aproximadamente 15,000 acres de tierras de las antiguas reservas. Un resultado menos tangible, pero igualmente importante, fue la disminución del orgullo y la herencia cultural de los Paiutes.
A principios de la década de 1970, los Paiutes comenzaron esfuerzos concertados para recuperar el reconocimiento federal. Finalmente, en 1980 el Congreso restauró la relación de fideicomiso federal con las cinco bandas, que se reorganizaron como la Tribu India Paiute de Utah. Bajo restauración, los Paiutes recibieron 4,770 acres de tierra de reserva generalmente marginal dispersa por el suroeste de Utah, solo una fracción de la tierra que habían perdido bajo terminación. Hoy en día, el gobierno tribal de Paiute ha mejorado la atención médica y la educación en las reservas, y el Desarrollo Económico de Paiute está trabajando para crear oportunidades de trabajo cerca de casa. Con una base terrestre ahora en su lugar, los Paiutes finalmente se están convirtiendo en una presencia visible en el sur de Utah. Su Reunión anual de Restauración llama la atención sobre el orgullo y la herencia del pueblo Paiute.