Utter was born in 1838 near Niagara Falls, New York, and grew up in Illinois, then traveled west in search of his fortune, becoming a trapper, guide, and prospector in Colorado in the 1860s.

In Cheyenne, Wyoming, famed gunman "Wild Bill" Hickok became partners with Utter in the train; Calamity Jane joined in Fort Laramie.

In February 1879, Utter purchased the Eaves Saloon in Gayville, a mining town 1.75 miles (2.82 km) west of Deadwood, but ran into a string of bad luck.

[citation needed] Later that year, Utter opened a dance hall in Lead, a company town far more sedate than its raucous, rollicking neighbor, Deadwood.

[5] On September 26, 1879, a fire devastated Deadwood, destroying more than three hundred buildings (including Charlie's dance hall and the theater he managed) and consuming the belongings of many inhabitants.

Following the destructive fire, Deadwood ceased to be a frontier town where fortunes could be built (or rebuilt) from nothing, and the newly impoverished left to try their luck in other gold rushes.

[citation needed] Utter cut a notable figure; he was 5'6" (167 cm), and was reported as being meticulous in his appearance, highly unusual for that place and time.