John Work, an agent for The Hudson's Bay Company, established Fort Colvile near the Kettle Falls fur trading site in 1825. It replaced the Spokane House and the Flathead Post as the main trading center on the Upper Columbia River.
Americans also wanted to operate in this territory. In the first half of the 19th century, the Oregon boundary dispute (or Oregon question) arose as a result of competing British and American claims to the Pacific Northwest. It was settled by the Oregon Treaty of 1846, which set the new boundary between Canada and the United States at the 49th Parallel, to the north of Fort Colville. The post continued to be used for some time as a center of mining and transportation/supply support associated with gold rushes in the 1850s and 1860s, particularly with the Holcomb Valley Gold Rush in California. After it was abandoned in 1870, some buildings stood until as late as 1910. The site was flooded by Lake Roosevelt after construction of the Grand Coulee Dam on the Columbia River.
The Kettle Falls Archeological District, including 17 pre-contact sites, as well as Fort Colville and St. Paul's Mission, were added to the National Register of Historic Places in 1974. Some archeological studies were done in the 1960s when the lake was lowered for additional dam construction and others have been undertaken. The district is highly significant to pre-contact and later Native American and United States history.
In 1859, the U.S. Army established a new Fort Colville at Pinkney City, about 3 miles NE of the current city of Colville. That fort was abandoned in 1882. In late 1871, with the resolution of Hudson Bay Company land claims, Governor Edward Selig Salomon directed John Wynne to accept those lands, including those currently part of the City of Colville. City development moved to the present location in the Colville River Valley prior to 1882. In January 1883, W. F. Hooker filed the first plat in Stevens County with the name "Belmont" or "Bellmond." He was encouraged to change the name to Colville, so that the county seat could be moved to this location. On December 28, 1883, the Stevens County Board of County Commissioners, including county commissioner John U. Hofstetter, held a special session regarding the removal of county records to Colville from the county seat of Pinkney City. In that meeting, commissioners allowed moving the city jail to Colville, if proprietors provided a block of land for county offices. County officers were allowed to move into a building owned by John U. Hofstetter. On January 1, 1884, the Stevens County courthouse moved to Colville. City tradition says that Colville was founded by John U. Hofstetter. It was officially incorporated as a city on June 7, 1890.
In the 1950s, the Colville Air Force Station was developed and operated in the hills above the city as part of the Air Defense Command's network of radar stations. A few buildings remain at the site today. It is used largely by paint-ballers.