The layover of General Howard's command on the shores of Henry's Lake coincided with a broadening of the army's pursuit of the nontreaty Nez Perces. After Henry's Lake, matters became increasingly complex for both the troops and the tribesmen. As Howard pursued, a military cordon slowly began to encircle the tribesmen on north, south, and east. This envelopment was composed of commands from the departments of Dakota and the Platte, overseen, respectively, by Brigadier Generals Alfred H. Terry and George Crook. On August 13, on Sherman's authority, Lieutenant General Sheridan directed Terry to cooperate with Howard, "even to temporarily placing such troops as you may have to spare under his command." At Camp Brown, Wyoming, Crook was alerted to the approaching Nez Perces and his men prepared for field duty. When Howard expressed concern that the Indians might be intending to join Sitting Bull's Sioux somewhere below the Canadian line, Sheridan responded that "such junction is preposterous." Yet to forestall efforts by the Nez Perces to gain a foothold in the Yellowstone country, Terry directed that troops be sent to watch the area of the Musselshell River and Judith Basin above the Yellowstone. 
In fact, such efforts were already underway. At the Tongue River Cantonment (soon to be known as Fort Keogh) on the Yellowstone, Colonel Nelson A. Miles, as early as August 3, had sent First Lieutenant Gustavus C. Doane with Company E, Seventh Cavalry, and about sixty Crow scouts to the Musselshell River to watch for signs of the Nez Perces. According to a directive to Doane, the lieutenant was to "use every effort to either capture or destroy the Nez Perces band of hostile Indians that have recently been engaging the troops in Idaho, and who will doubtless, if defeated, endeavor to retreat and take refuge in the Judith Basin or vicinity."  Of major concern at this juncture was maintaining the allegiance of the Crows, and Doane was expected to use whatever diplomacy he could muster to that end.  On the twelfth, underscoring Miles's determination to stop the Nez Perces, he sent Colonel Samuel D. Sturgis with six companies of the Seventh Cavalry up the Yellowstone to observe the country about the Judith Basin, some 250 miles northwest of the Tongue River post.  Another directive to Doane asserted:
Seven days later, Sturgis deployed his force on the Musselshell, but shortly removed to the mouth of the Stillwater River on the Yellowstone "with a view of taking up a central position where we might guard the various passes by which the Indians might attempt to debouch from the mountains."  Sturgis also received notice from Howard stating that, based on information from his scouts, the tribesmen "will probably cross Stinking [Water] River one hundred miles south east of Crow Agency."  Much against Sturgis's wishes, Lieutenant Doane, acting on orders received from Colonel Gibbon, moved his scouting force to Fort Ellis and, on August 29, set out for the upper Yellowstone leading into the national park. 
All the while that Howard's troops and animals had been resting at Henry's Lake, his Bannock scouts trailed the Nez Perces east through Targhee Pass, across the valley of the South Fork of the Madison, and into the national park. There, along the main Madison River on August 25, they came upon two men, William H. Harmon and Charles Mann, whose party had been captured the previous day by Nez Perce warriors. This information, plus news of the general course of the Nez Perces relayed to Howard on his return from Virginia City, confirmed in his mind that they were headed for the Crow Agency near the Yellowstone River and ultimately for the buffalo grounds above that stream. "I believed that the route of the enemy, conforming to the features of the country, would be through [the] National Park to Musselshell Valley, by way of Clarke's [sic] Fork, or possibly leading further south by way of some point between Crow agency and the Stinkingwater [present north fork of the Shoshone River], crossing to the valley of the Musselshell."  It was in looking to the possibility of heading off the tribesmen that Howard had sent Captains Harry C. Cushing and Norwood to Fort Ellis. Those troops had instructions to keep Howard posted and to communicate with Colonel Sturgis's patrolling command. 
As Howard pondered the Nez Perces' objective points, unknown to him General Sherman, following up on his previous communication with Howard, and possibly in response to continually mounting criticism of his brigadier, had set in motion plans to gently remove him from command. On August 29, from Helena, Sherman wired Sheridan:
Two days later, Colonel Gilbert departed Fort Ellis with Company L, Second Cavalry, now under command of Second Lieutenant Charles B. Schofield, to find Howard and take over the general's column in accordance with Sherman's wishes. 
The missive Gilbert carried to Howard outlined the troop dispositions underway in Sheridan's division and noted that his column, as the "pursuing force," had "not much chance of a fight." In it, Sherman continued:
The effort by Sherman to remove Howard reflected not only the commanding general's deep-seated frustration toward the overall progress of the campaign, but also his extreme anger at the Nez Perces themselves. His harsh views toward the Nez Perces were evident in a telegram to Sheridan sent from Deer Lodge on August 31:
Oblivious to all this, Howard, on Tuesday morning, August 28, pulled out of camp at Henry's Lake. There the Montana volunteers departed, as did most of the wagons hired in Missoula. The command marched through Targhee Pass to the Madison River, on the very course the tribesmen had taken six days before. As the troops coursed up the Madison, they encountered "a most wretched figure, worn and ragged." He was Henry Meyers, another escapee from among the same group of tourists accosted by the Nez Perces four days before at Lower Geyser Basin. Later, yet another man, Albert Oldham, appeared, having been shot in the face by the warriors and in a "famished condition."  Howard camped that night on the Madison River, leading into the park.
The national park, informally called "Wonderland" because of its variety of natural features ranging from vast and nearly impenetrable forests intertwined with lakes and streams to unique geologic formations and abundant thermal phenomena, had been established by Congress in 1872 "for the benefit and enjoyment of the people." The park then encompassed nearly 3,313 square miles, principally in northwestern Wyoming Territory (the west and north boundaries were in Idaho and Montana territories, respectively), running approximately sixty-two miles north-to-south by fifty-four miles east-to-west. Besides the Madison and its contributory streams, the Gibbon and the Fireholeencountered by the Nez Perces as well as by Howard's command as they proceeded into the parktwo major rivers draining the area were the Yellowstone, flowing northward through the park to form high-altitude Yellowstone Lake, and the East Fork of the Yellowstone (later named the Lamar River), which converged with the primary stream in the north-central part of the park as it angled northwest and beyond the boundary. Numerous affluents joined these streams everywhere as they coursed across the mountainous park topography. In 1877, there were no major roads and few trails leading through the Yellowstone wilderness, although wagons traveling up the Madison and Firehole rivers could reach the area of the Lower Geyser Basin. Across the Yellowstone River, above its confluence with the East Fork (Lamar), a wooden bridge had been erected by Collins J. ("Yellowstone Jack") Baronett, enabling travel between Mammoth Hot Springs, where a log cabin hotel stood for the benefit of tourists, and the route east to the mining region around Cooke City.  All of the activity related to the Nez Perces and Howard's army in that year took place in the northern half of the national park.
Oddly enough, as the course of events unfolded, the pinnacle of army leadership had left the national park just days before the Nez Perces entered it. Commanding General William T. Sherman, on a tour of western posts during the summer of 1877, had left Fort Ellis on August 4 with an entourage of two officers besides himself, his son, a packer-guide, three drivers, and only four soldiers, a total of twelve persons. "I do not suppose I run much risk," he wrote Secretary of War McCrary, "for we are all armed, and the hostile Indians rarely resort to the park, a poor region for game, and to their superstitious minds associated with hell by reason of its geysers and hot springs." 
From August 6 to 17, Sherman's group ranged through the north and west parts of the park, visiting Mammoth Hot Springs, Mount Washburn, the Lower Falls of the Yellowstone and the geyser basins, and Old Faithful, impressed by its beauty and geologic features. At Mud Volcano, the general's people peered inside the boiling, churning enigma, deciding it was not of volcanic origin but of "muddy water, and . . . thick mud, puffing up just like a vast pot of 'mush.'"  On August 16, they were overtaken by a courier bearing news of Gibbon's battle at the Big Hole, and the next day, en route back to Fort Ellis, Sherman's party received dispatches, telegrams, and newspapers describing the event. Back at the post on August 19, the commanding general wrote McCrary that "we saw no signs of Indians, and felt at no moment more sense of danger than we do here." 
Sherman had no knowledge of his proximity to the Nez Perce cavalcade that entered the park only six days after the general's party had vacated it. On Tuesday, August 21, the tribesmen camped at Henry's Lake, their livestock fairly blanketing a three-square-mile tract as it grazed. On the following day, the people filed into Madison Basin along the road from Virginia City to the Lower Geyser Basin, their presence creating a brief scare along the Madison Valley as panicky residents fled toward Virginia City. That night a party from the Nez Perce camp raided a small band of miners twenty miles away along the West Fork of the Madison and got away with most of their horses.  The arrival of the Nez Perces in the national park on August 23 opened to them a myriad of possibilities regarding their course throughout it and egress from it. One of the army's principal authorities on the park was Colonel John Gibbon, who had explored the region on a visit in 1872, subsequently lecturing and authoring articles describing its wonders for the public.  On Sherman's direction, he offered Howard his views of the route the tribesmen might take:
Gibbon proved correct in predicting at least part of the Nez Perces' route. It is apparent that the people themselves, for a major portion of their trek through the park, remained uncertain of their course. Few Nee-Me-Poo accounts addressed the matter of their route, and whatever clues to the mystery of where they went have been derived from non-Nez Perce sources, principally from the account of Howard's leading scout, Fisher, who with the Bannocks trailed them for much of the way, and that of John Shively, a prospector who was captured and held by the Nez Perces during their passage (and then escaped). It is the latter stage of the people's course through the park that is open to question and has been the focus of considerable debate.