Brigadier General William S. Harney, commander of the Department of Oregon, opened up the district north of the Snake River to settlers in 1858 and ordered Brevet Major Pinkney Lugenbeel, 9th Infantry Regiment to establish a military post to restrain the Indians lately hostile to the U.S. Army's Northwest Division and to protect miners who flooded into the area after first reports of gold in the area appeared in Western Washington newspapers in July 1855.

[1][2] It was common practice to use existing Indian trails to develop military roads, and only make necessary improvements for the movement of artillery or supply trains.

Washington Territorial Governor Isaac Stevens and the U.S. Army were ordered by the U.S. Department of State to honor land ownership claims by the Hudson's Bay Company.

[7] Major Lugenbeel was appointed special agent for the Indians in the region located near Fort Colville.

[8][10] Brevet Major Lugenbeel was directed to build a four-company post able to house 300 men and the U.S. Northwest Boundary Commission personnel.

[11] The U.S. Northwest Boundary Survey personnel arrived at the fort on December 3, 1859, but the buildings assigned to them were not complete.

Locals considered these troops, with some recruited from Alcatrez Prison, as a bad lot including one of the fort's lieutenants who murdered John Burt.

[17] On November 3, 1865, regular troops G Company, 14th Infantry Regiment of the U.S. Army, returned to man the fort.

[19] On February 18, 1867, soldiers of G Company killed Deputy Sheriff Horace P. Stewart as he tried to break up a beating of his business partner, Jack Shaw, at the saloon owned by both men.