The City of Red Deer was named after the river which flows through it. The Cree called the river Waskapoo Seepee, the Aboriginal name for "Elk River." The river received this name because of the numerous elk frequenting its banks in the early days. In the early 1870s, Métis buffalo hunters established themselves in settlements along the Red Deer River. In the mid-19th century, the Blackfoot, the Stoney, the Plains Cree and the Métis lived in the area. Early European fur traders often mistook the elk as a type of European red deer. They mistranslated the Cree name Waskapoo Seepee for "Red Deer River." Later on, settlers to the area referred to their community as Red Deer.
Addison McPherson was the first European to live in the district. In 1872, he built a trapper's log cabin about five kilometres southwest of the present city. In 1875, traffic increased along the trail due to the building of Fort Calgary by the North West Mounted Police. In the summer of 1882, permanent settlement into the area began.
In the spring of 1884, Reverend Leonard Gaetz, with his wife and 10 children, took up a homestead on a section where the city of Red Deer now stands. Reverend Gaetz heard of the agricultural potential of the Red Deer River Valley from his friend. During the Rebellion of 1885, the Canadian militia fortified an existing building, Fort Normandeau, at the Red Deer crossing settlement. This post was later taken over by the North West Mounted Police who used it until 1893. When the Calgary and Edmonton Railway bypassed the crossing entirely, its settlers abandoned the crossing and moved east to present-day Red Deer.