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.