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.