Fort Duchesne was established by Major Frederick William Benteen on 20 August 1886, on a site selected by General George Crook, and General Crook soon took command of the new fort. Construction began in October 1886 and the reservation was officially designated by President Cleveland in September 1887. The fort continued to serve, with an average detachment of 250 men, until its closure in September 1912. Remnants of the fort still exist.

Fort Duchesne was established to replace Fort Thornburgh in the Uinta Basin, which had been abandoned by the U.S. Army during the winter of 1884-85. An outbreak of inter-band warfare among the Utes during the winter of 1885-86 once more raised the question of placing a fort in the basin. The Department of the Interior and the War Department each sent investigators to the area who recommended the establishment of a permanent fort. Crook selected the site in August 1886; it was three miles above the junction of the Uintah and Duchesne rivers and midway between the Whiterocks agency and Ouray agency headquarters.

Major Benteen led two troops of the Ninth Cavalry from Fort McKinney, Wyoming, and a Captain Duncan led four companies of infantry from Fort Steele, Wyoming, onto the Ute Reservation to establish the fort. The cavalry troops Benteen led into the Uinta Basin were a detachment of the Ninth, which was a Black cavalry unit that served on the Uintah frontier for twelve years. With the outbreak of the Spanish-American War, the Ninth was sent to Cuba in 1898. The soldiers of the Ninth were highly decorated during that war, and were among the men who followed Colonel Theodore Roosevelt up San Juan Hill.

While Benteen's men reached the fort site without incident, Duncan's infantry barely escaped disaster. As Duncan's men prepared to take a shortcut, a Ute policeman rode up on a well lathered horse and informed Duncan that nearly three hundred Utes lay in ambush for his men. Duncan decided to march via the longer, regularly traveled road, and arrived at the fort site without incident.

When the combined forces arrived at the fort site, they were confronted by a force of 700 Utes. The soldiers quickly threw up a picket line and began to dig defensive trenches. These proved to be unnecessary when the Utes became convinced that the army would not attack them as long as they remained passive. By October, the soldiers had settled into the routine and business of the camp and its construction.

President Grover Cleveland officially designated the six square miles that comprised the fort reservation on 1 September 1887. During the summer of 1887, the troops spent approximately $22,800 on construction of the fort. This included the construction of officers' and enlisted men's quarters, a commissary, a storehouse, and a hospital, all of adobe brick. Establishment of Fort Duchesne caused the War Department to again evaluate the need for the string of small western forts. Fort Steele was abandoned in 1886 when the troops left for Uintah County, and Fort Bridger was abandoned in 1890. Fort Duchesne was designated to guard the Indian frontier in eastern Utah, western Colorado, and southwestern Wyoming.

Fort Duchesne declined in use from 1890 to 1910. In 1893 the four infantry companies were removed to Fort Douglas. By 1909 there was only one company of cavalry left. In 1910 the inspecting officer of the U.S. Army "found no military reason why Fort Duchesne, Utah should be continued as a military post." On 13 September 1912 Troop M of the First Cavalry, the last remaining unit at the reservation, left Fort Duchesne for Fort Boise, Idaho. The Indian Service consolidated its Uintah and Ouray operations at Fort Duchesne after the fort's abandonment by the army. The buildings that had been constructed to control the Indians were at last used to assist them.