Another fort, Fort Kearny, was involved in a very violent conflict between Americans and Native Americans in 1866. A U.S. Cavalry force went up against a force of Arapaho, Cheyenne, and Sioux, led by Crazy Horse and Red Cloud; the result, at the Battle of the Tongue River, was a resounding victory for Native Americans. Red Cloud's War followed and was ended by another treaty.

One of the most famous residents of Wyoming was William "Buffalo Bill" Cody. He founded the town of Cody, near Yellowstone, and became known across the country and in Europe for his Wild West Show, which featured Annie Oakley. Two other more infamous residents of Wyoming for a time were the outlaws Butch Cassidy and Harry Longabaugh (the Sundance Kid), members of the Wild Bunch, who were also for a time associated with another group of outlaws known as the Hole-in-the-Wall Gang.

The Union Pacific Railroad reached Cheyenne in 1867 and eventually connected the territory's largest cities. Discovery of coal in southwest Wyoming facilitated this.

Congress established the Wyoming Territory in 1868. The next year, Wyoming became the first government in the world to grant women the right to vote. The territory was also the first in which women served on a jury and a woman was a justice of the peace (Esther Hobart Morris).

Wyoming became the 44th state in the Union on July 10, 1890.