Among the other units, Captain George L. Tyler (1839-1881) had served with state troops during the Civil War, with the regulars since 1866, and had been with the Second Cavalry since 1870. Both of his subalterns, Edward J. McClernand (1849-1926) and Lovell H. Jerome (1849-1935), graduated from the military academy in 1870 and had been with the Second since then. Of the Fifth Infantry officers, Simon Snyder (1839-1912), who commanded the mounted battalion, had served with the regiment since 1861 and as a captain since 1863. Captain Andrew S. Bennett (1834-1878), a Wisconsin infantry officer during the Civil War, joined the Fifth regulars in 1871 (he would be killed in action with Bannock Indians within a year), while his second lieutenant, Thomas M. Woodruff (1848-1899), had been with the regiment since his 1871 graduation from West Point. Mason Carter (1834-1909), commanding Company B, a Georgia native who fought on the Union side in the Civil War, had been a first lieutenant with the Fifth since 1864. First Lieutenant Henry Romeyn (1833-1913), a breveted Civil War veteran, had joined the regiment in 1869 in that grade. Of Miles's staff, Adjutant George W. Baird (1839-1906) had ended the Civil War as a commander of black troops and joined the Fifth Infantry in 1869, while Second Lieutenant Marion P. Maus (1850-1930), an 1874 academy graduate, was attached to Miles's command from the First Infantry. Second Lieutenant Oscar F. Long (1852-1928), an 1872 West Point graduate, had served with the Fifth Infantry since June 1876. Major and Surgeon Tilton (1836-1906) had served in the army since the start of the Civil War, while Assistant Surgeon Gardner had joined the regular army only in August 1876. 
Many of Miles's officers and men, while new to the Nez Perce war, represented seasoned campaigners recently involved in arduous campaigns against the Teton Sioux and Northern Cheyennes. Following the disaster at the Little Bighorn that had decimated the Seventh Cavalry, Miles had led his Fifth infantrymen on lengthy and successful campaigns in the Yellowstone-Missouri wilderness, meeting the warriors in several pitched encounters that had contributed to the collapse of the Indian coalition early in 1877. His troops, augmented by a battalion of Second cavalrymen from Fort Ellis and part of the reconstituted Seventh regiment from Fort Lincoln, had spent the spring and early summer in running down small groups of tribesmen as they fled from or to the agencies or sought to reach Sitting Bull's people in Canada. Weathered and worn from their weeks afield, Miles's force was nonetheless tried, vigorous, and overtly optimistic in the fashion of its commander as the men set out after the people now commonly referred to as "Joseph's Nez Perces."
On Tuesday, September 18, the departing command passed through the camp of captive Sioux and Northern Cheyennes, who had surrendered to Miles the preceding March, as the troops made their way nearly eighteen miles northwest up Sunday Creek, an affluent of the Yellowstone, before halting at 5:00 p.m. The march was not easy because the train had difficulty negotiating the prevalent quicksands of the alkaline stream. Cognizant of Sherman's stricture against crossing north of the Missouri, Miles expected to confront the Nez Perces before they reached the river; his immediate objective, therefore, was to gain the mouth of the Musselshell River on the Missouri in the shortest time possible and work accordingly from that point. He sent a directive to Captain Tyler, out ahead with his battalion of Second Cavalry en route to General Terry, to unite with Hale's company of Seventh Cavalry and together to keep watch for the Nez Perces and exercise vigilance to prevent surprise. Miles proposed meeting Tyler's command at the Musselshell. 
On Wednesday the command continued tracing the stagnant pools that comprised Sunday Creek, the landscape turning into badlands as they passed seventeen more miles and stopped early in the afternoon on a branch of the stream to await the wagons, which arrived two hours later. That night they subsisted on buffalo, deer, and antelope, but had poor-quality water and built their fires from buffalo chips, the only fuel available. The twentieth saw them off at 5:15 a.m., proceeding northwest through the "dreary waste" of the divide between the Yellowstone and Missouri rivers, a parched, treeless scape deprived of all water but for rain-caused pools. Atop the divide, they "obtained a most perfect view of the varied and extensive scenery of the surrounding country," before camping on a tributary of the Big Dry, having traveled thirty-one miles.  That evening, thirty Northern Cheyenne warriors joined the command from the camp near the cantonment to serve as scouts for Colonel Miles. Miles increasingly used his civilian and Indian guides as he neared the zone where he might logically expect word of the Nez Perces, and felt constantly to his left front with what he called "a cloud of scouts and videttes" during his movement to the Missouri. 
On September 21, the troops arrived at the southern branch of the Big Dry River"the first running-water stream since leaving the Yellowstone," wrote Lieutenant Long. Along the cactus-and-sage-strewn prairie this cloudy day at noon, they reached the four Second and Seventh cavalry companies, halted since receiving Miles's directive not to proceed to Fort Benton. The command bivouacked along a stream with alkaline water and plentiful game but without timber, again awaiting the wagons and escort. On the following day, Saturday, great herds of buffalo came in sight, but Miles had issued an order to prevent the firing of weapons. "No shooting was allowed," wrote Private William F. Zimmer, "for fear of stampeding them and putting the Indians on their guard, if there is any near."  "The lumbering fellows act as if they had received a copy of the order," observed Dr. Tilton. "They cross our trail, running between the advance guard and the next battalion."  The travel was difficult, the road winding among arroyos and through barren hills as the soldiers transected various tributaries en route to Squaw Creek, finally camping long after dark amid towering cottonwood groves, having covered thirty-six miles.
On Sunday, the twenty-third, the troops moved five miles, camping on Squaw Creek within sight of the high bluffs of the Missouri. Anxious that he might be delayed in crossing the river, Miles sent Lieutenant Biddle of the Seventh Cavalry with five enlisted men ahead to stop a passing steamboat to ferry the Second Cavalry battalion to the north side. Later, a courier from Biddle announced that a vessel, Fontenelle, en route from Fort Benton to St. Louis, awaited Miles's use. Moreover, the boat's captain had no knowledge of the Nez Perces having crossed above, so Miles believed he was still ahead of them. Dispatches also arrived from Tongue River with news of Sturgis's encounter with the tribesmen at Canyon Creek, terming the action "a running fight from the Yellowstone to the Musselshell." Howard told Miles of his intention to slow his own march to allow the colonel sufficient time to advance his force.  After marching about twenty-two miles, the command reached the mouth of Squaw Creek on the Missouri at 7:00 p.m., about six miles below the mouth of the Musselshell. As the soldiers went into camp, scout George Johnson ill-advisedly tried to cross the river and drowned.  Despite this loss, the mood remained high. Wrote Lieutenant Long: "Since leaving the Yellowstone we had marched 146 miles, and the miserable water from the alkalescent to the strongly alkaline had begun to tell on men and animals, but the refreshing draughts of the pure Missouri River water served to reinvigorate to restore the spirit and animation, and to relieve the fatigue."  And Lieutenant Biddle wrote home: "I think Joseph has had so many hard knocks . . . that he will surrender if he finds this command ahead of him." 
At the Missouri, Miles made plans to start Tyler's battalion to Fort Benton for Terry's commission to Sitting Bull, telling him, however, "should you en route find any indications of the Nez Perces having crossed the Missouri, you will use your force to intercept, or pursue them."  At the mouth of Squaw Creek, Miles therefore crossed only Tyler's men and their train of twelve wagons on the Fontenelle, and used the steamer to begin transferring his own supplies and the artillery to the left bank of the Musselshell on the Missouri, leaving the rest of his wagons at Squaw Creek with Captain Brotherton's company. Still laboring in the conviction that the Nez Perces would most likely be encountered south of the river, he wrote Terry: "I will move up on the south side of the Missouri to Carroll, and possibly Judith Basin, to intercept and, if possible, prevent any of the Nez Perces from going North."  Thus intending to go on west below the Missouri, Miles outfitted his troops with fifteen days' rations and began a complicated and complex movement to get them and their horses and pack animals across the Musselshell.  Lieutenant Long described the situation on September 24 in excruciating detail:
During the night of the twenty-fourth, the steamer Benton passed up the Missouri, dropping off Miles's adjutant, Lieutenant Baird, with the provisions he had arranged for at Fort Peck, eighty miles down the river. Two of Miles's scouts, Luther S. "Yellowstone" Kelly and George Abbott, also joined from Bailey's detachment at Carroll.  Meanwhile, the Fontenelle completed transferring Miles's supplies and, by early the morning of September 25, had departed downstream. Then, as the troops gathered near the Missouri, a small boat arrived from above bearing a note penned that morning by Lieutenant Bailey at Carroll:
Clendenin's letter, of course, told of the Nez Perces' sacking of the stores at Cow Island after they crossed the Missouri at that point on the twenty-third, as well as their likely course to the border: "I think the Nez Perces are keeping up Cow [Creek] & will pass through the [Little] Rockies & Bears Paw & so north to the line." 
The news brought an abrupt change in Miles's strategy. He abandoned his plan to continue along the south bank and decided to cross over and prolong his trajectory northwest, now intent on intercepting or pursuing the Nez Perces somewhere in the area of the Little Rocky or Bear's Paw ranges. "I decided to place my force as speedily as possible in the gap between the northern ends of the Little Rocky and Bear Paw Mountains, between which ranges the Indians had started northward," he reported.  Immediately, he directed Sergeant McHugh to fire three rounds from the Hotchkiss gun as a signal to the Fontenelle, by then several miles below the command. Lieutenant Baldwin, aboard the steamer sick with pneumonia that precluded his further involvement in the campaign, heard the distant firing and the shots bursting in the air and ordered the vessel turned about.  The rest of the day and night was spent in transferring Miles's entire command, including pack train and wagons, to the north bank in preparation for renewing the pursuit. Kelly and the civilian scouts rode far ahead, seeking a tall butte from which to scan the horizon. Shortly after dark, the Second Cavalry battalion started for Fort Benton, still intent on joining Terry's commission.  On Wednesday, a cold and windy day, Miles wrote his wife: "We start right north for the Little Rocky and Bear Paw Mountains with the hope of heading them off or getting on their trail. I intend to move as rapidly as possible."  After a difficult labor getting the wagon train up from the river bottom, Miles and his troops marched away from the Missouri, covering fifteen miles before bivouacking among the low hills of a gradually ascending plateau. "To the northwest the blue outline of the Little Rocky Mountains is seen," noted Lieutenant Long. 
On September 27, Miles and his troops reached Fourchette Creek, gradually ascending that stream and its Dry Fork toward the northeast end of the Little Rockies. The view was spectacular. "To the east and west of us," wrote Long, "as far as the eye can see, stretches a vast expanse of undulating prairie land, with waving grasses that furnish food for the numerous herds of buffalo and antelope that graze on every side."  After traveling less than ten miles, the troops overhauled Tyler's battalion. Miles "put a stop to our movement," wrote Private Zimmer, and the companies formally merged with his field command. They all stopped to await arrival of the train, and the horses and mules were allowed to browse. "While our stock is grazing, a few buffalo quietly join the herd, to seek the refining influence of government mules," noted an officer. "For fear that they may stampede [our] flock, orders are given to shoot them."  Surgeon Tilton celebrated the "swift running mountain streams of palatable water, which were a Godsend to us." 
Late that afternoon, leaving his wagons and the Napoleon gun with forty soldiers under Captain Brotherton and Lieutenant Borden, Miles pulled away with his mounted force, rationed for eight days, plus the Hotchkiss gun and pack train, passing through the gently rolling lands of upper Dry Fork Creek, probably but a few miles west of present Shed and Beam lakes. Tilton noticed an abundance of ducks; "some are lighting and dashing the spray. . . . Others are . . . taking wing. They need have no fear; we are not hunting ducks today."  With the scouts well out in front, toward evening the men entered the low foothills of the Little Rockies, camping long after dark without wood and near some holes containing rainwater "thick with mud." The distance traveled this day was little more than twenty-four miles.