After his victory over Col. John Gibbon at Big Hole, Joseph through masterful countermoves and deception, continued to elude General Otis. Howard who they called "One Armed Soldier Chief', and headed out of Yellowstone National Park toward Crow Country and a hopeful alliance with their old friends. The Crow's however had served Gibbon and Custer faithfully as U.S. Indian Scouts the summer before and would do so again. Even the Assiniboine and Cheyenne (the later enlisted as U.S. Indian Scouts) would turn against the Nez Perce. Sturgis meanwhile marched to the mouth of Clark's Fork to block the Nez Perce. Skillful maneuvering and deception soon proved a match for Sturgis, who left Clarks Fork for the vicinity of Stinking Water (Shoshone River) while Joseph headed through the Sevenths former camp and on to the plains and Yellowstone valley with a 45 mile head start.
Now the only obstacle between them and the freedom of the Canadian border was Sturgis and Miles; two army colonels who would like Howard and Gibbon, be put to the ultimate test of their fighting ability and the endurance of their men and horses. Although he didn't admit it in his official report, Sturgis had underestimated Joseph and he had been tricked by the skillful maneuver of the Nez Perce. Private Jacob Homer, Sturgis' orderly spoke freely of it as did others in the regiment especially Captain Benteen.
Feeling confident that they had out distanced the soldiers, Joseph slowed their pace. Sturgis in the meantime had reported to Howard and requested reinforcements. After picking up the Nez Perce trail about 12 miles from the outlet of Stinky River on Clark's Fork Canyon, the Seventh began a two day forced march in drizzling rain in an effort to overtake the Nez Perce who had a two day head start on them. At mid day, a halt was made and officer's call sounded. Benteen suggested to Sturgis that there was one way to overtake the Indians, "By marching forty miles that day and fifty the next if necessary." Sturgis embarrassed by his earlier blunder at Clark's Fork, consented and soon pushed men and horses to the very limit of endurance; 48 miles on August 11th until the horses were almost run into the ground! By 10 AM (September 13th) Sturgis finally halted.
Benteen growing frustrated with the lack of progress in overtaking the Nez Perce requested permission to go on independently with three companies without the slower moving pack mules. Sturgis, denied Benteen permission showing caution and restraint after the recent defeat of Gibbon here at Big Hole, and remembering the painful lesson that the regiment learned at Little Bighorn when Custer divided the 7th and overextended the command, which had ultimately contributed to the regiments defeat and the loss of his son.
Renewing the march, the Seventh reached the Yellowstone River and crossed over to the north side. While waiting for the slower pack mules and rear guard to cross over, smoke was observed down the valley and a Crow scout reported that the Nez Perce were downstream and attacking. The Nez Perce had attacked and burned a stage station, captured a stagecoach taking it for a brief ride over the prairie, and set fire to some haystacks.
Sturgis, taken completely by surprise ordered the trumpeters to sound "To Horse" and advanced at a trot down river. After advancing about two miles, it was learned that the Nez Perce were moving rapidly to the northwest up Canyon Creek the head of a large 200' high canyon of sandstone, that is approximately 10 miles from the Yellowstone, just north of present day Laurel, Montana.