In 1857 President James Buchanan decided to name new officials for Utah Territory and to send with them a military escort to ensure their authority. In May, 2,500 troops were assembled to be dispatched to Utah. General William S. Harney was originally designated to head the campaign, but conditions in "Bleeding Kansas" caused him to remain in that state. In late August, Johnston was assigned charge over the expedition, now well on its way to Utah; but he didn't catch up with the troops until November. In the meantime, these events caused anxiety among the Utah Mormons, who believed that the United States was sanctioning their destruction.

On 15 September 1857 Brigham Young, Governor of Utah Territory, issued a decree that forbade entry of armed forces into the territory, and declared martial law. Young mobilized the local militia, known as the Nauvoo Legion. Army troops began to arrive at Ham's Fork on 28 September, commanded by Colonel E.B. Alexander. On 5 October, Lot Smith and his band of Mormons attacked and destroyed fifty-two wagons of U.S. Army provisions. On 3 November, Johnston caught up with his forces and pushed on to Fort Bridger, renamed Camp Scott, and prepared camp for winter.