When the plains near present-day Great Falls began to rise into the first foothills of the Rocky Mountains, the expedition continued upstream by boat on the Missouri River. As they traveled, they passed a flat-topped landmark now known as Square Butte, which they called Fort Mountain, and then moved into a country of deeper valleys and canyonlike walls. Eager to find signs of Sacagawea's Lemhi Shoshone people, Captain Clark left the main group with a small party to scout overland while the rest stayed with the boats.

On July 19, 1805, the expedition entered a dramatic three-mile stretch of river the captains named the Gates of the Mountains. There the Missouri flowed between steep cliffs of limestone that, in places, rose about 1,200 feet above the water, seeming to close like great stone doors as the boats rounded each bend. Today this part of the river has been widened into a reservoir by a dam downstream, but visitors can still see the tall cliffs and imagine the view Lewis described in his journal that day.