As the State was explored and settled by Euroamericans, it became necessary to connect one place of settlement to another. The Native Americans had numerous trails that they used, some of which had developed from animal paths. The Fur traders and the oxcarts that traveled between Winnepeg and St. Paul created other networks of trails, but as settlement increased there was a need for better maintained roadways.
Early roads established by the federal government were built to "facilitate the business of government". Establishing routes between military posts was the first order of business. In 1820 efforts were made to establish a road between Fort Snelling and Camp Missouri (located near present day Omaha, Nebraska), but surveys did not find a good route. In 1836 the U.S. Congress appropriated $100,000 to fund a road to connect the Red River of the North with Arkansas. Captain Nathan Boone arrived at Fort Snelling to begin the survey work in 1838, but it was never completed.
Not until the 1850s were the first military roads built. A law requiring the Secretary of War to construct certain roads in the Territory of Minnesota was passed on July 18, 1850. They were as follows: the Mendota-Wabasha Road, the Point Douglas-St. Louis River Road, the Point Douglas-Fort Ripley Road and the Red River Addition, the Swan River-Long Prairie Road and the Mendota-Big Sioux River Road. The last which would have connected Fort Snelling to Fort Leavenworth, Kansas, was only completed to Mankato. Of the original 560 miles of military roads only small portions are still in use, as county and township roads. But those five roads formed the framework of the statewide network of roads that followed.