On June 15, 1866, soldiers under the command of brevet Lieutenant Colonel William G. Rankin commenced building a new fort in Dakota Territory. It was named after the late Major General John Buford, hero of Gettysburg. By the end of November, the finished fort consisted of a 360-foot-square stockade, enclosing log and adobe buildings, which was constructed to house a single company garrison.
Although historically the Fort Buford region was claimed by the Hidatsa, the Sioux controlled the area after the Hidatsa population was decimated by smallpox. The Sioux, angered by the establishment of the fort, attacked a work party at the sawmill on December 21, 1866. Raids continued sporadically throughout the winter. Post Surgeon James P. Kimball noted that these attacks were led by Sitting Bull.
During January, Rankin received orders that the strength of the garrison would be increased by four additional companies that would arrive in the spring. Construction of a larger fort to house the new troops began in 1867. The old stockade was partially demolished and original buildings were either remodeled or torn down. The new fort measured 999 feet by 600 feet and was enclosed on three sides by a twelve-foot stockade. Unfortunately, the buildings were constructed from handmade adobe bricks and green lumber, which causes deteriorations within three years. The deplorable condition of the buildings, as well as increased Indian attacks, necessitated the construction of an expanded fort in 1871-1872. As part of the third construction phase, the post was designed for ten companies but was ultimately built to house six companies.
While the fort construction was underway, the Northern Pacific Railway resumed survey activities west of the Missouri River. These Yellowstone expeditions of 1871-1873 and the Black Hills expedition of 1874 violated the Treaty of 1868. The Sioux were provoked and felt the president of the United States "must stop the railroad" because it would destroy or chase away wildlife. They would not let the invasion of their lands go unchallenged.
By late 1875, the situation had deteriorated to the point that the secretary of interior asked the secretary of war to force Indians onto their respective reservations. This action began the Sioux Wars of 1876-1879 that included the defeat of Custer at the Battle of Little Bighorn and Sitting Bull's flight into Canada. Sitting Bull struggled to maintain his independence, but lack of natural game for hunting and the desire of his people to return to their relatives led him to return to Dakota Territory. Thirty-five families, 187 people in all, traveled with Sitting Bull to Fort Buford, where on July 20, 1881, the great Sioux chief surrendered his Winchester .44 caliber carbine to Major D.H. Brotherton, Fort Buford's commander.