Burial mounds in present-day Indian Mounds Park suggest that the area was originally inhabited by the Hopewell Native Americans about two thousand years ago. From the early 17th century until 1837, the Mdewakanton Dakota, a tribe of the Sioux, lived near the mounds after fleeing their ancestral home of Mille Lacs Lake from advancing Ojibwe. They called the area I-mni-za ska dan ("little white rock") for its exposed white sandstone cliffs. In the Menominee language it is called Sāēnepān-Menīkān, which means "ribbon, silk or satin village", suggesting its role in trade throughout the region after the introduction of European goods.
Following the Louisiana Purchase in 1803, US Army officer Zebulon Pike negotiated approximately 100,000 acres (40,000 ha; 160 sq mi) of land from the local Dakota tribes in 1805 to establish a fort. The negotiated territory was located on both banks of the Mississippi River, starting from Saint Anthony Falls in present-day Minneapolis, to its confluence with the Saint Croix River. Fort Snelling was built on the territory in 1819 at the confluence of the Mississippi and Minnesota rivers, which formed a natural barrier to both Native American nations. The 1837 Treaty with the Sioux ceded all local tribal land east of the Mississippi to the U.S. Government. Taoyateduta (Chief Little Crow V) moved his band at Kaposia across the river to the south. Fur traders, explorers, and missionaries came to the area for the fort's protection. Many of the settlers were French-Canadians who lived nearby. However, as a whiskey trade flourished, military officers banned settlers from the fort-controlled lands. Pierre "Pig's Eye" Parrant, a retired fur trader-turned-bootlegger who particularly irritated officials, set up his tavern, the Pig's Eye, near present-day Lambert's Landing. By the early 1840s, the community had become important as a trading center and a destination for settlers heading west. Locals called the area Pig's Eye (French: L'Œil du Cochon) or Pig's Eye Landing after Parrant's popular tavern.
In 1841, Father Lucien Galtier was sent to minister to the Catholic French Canadians and established a chapel, named for his favorite saint, Paul the Apostle, on the bluffs above Lambert's Landing. Galtier intended for the settlement to adopt the name Saint Paul in honor of the new chapel. In 1847, a New York educator named Harriet Bishop moved to the area and opened the city's first school. The Minnesota Territory was formalized in 1849 and Saint Paul named as its capital. In 1857, the territorial legislature voted to move the capital to Saint Peter. However, Joe Rolette, a territorial legislator, stole the physical text of the approved bill and went into hiding, thus preventing the move. On May 11, 1858, Minnesota was admitted to the union as the thirty-second state, with Saint Paul as the capital.
That year, more than 1,000 steamboats were in service at Saint Paul, making the city a gateway for settlers to the Minnesota frontier or Dakota Territory. Natural geography was a primary reason that the city became a landing. The area was the last accessible point to unload boats coming upriver due to the Mississippi River Valley's stone bluffs. During this period, Saint Paul was called "The Last City of the East." Industrialist James J. Hill constructed and expanded his network of railways into the Great Northern Railway and Northern Pacific Railway, which were headquartered in Saint Paul. Today they are collectively part of the BNSF Railway.
On August 20, 1904, severe thunderstorms and tornadoes damaged hundreds of downtown buildings, causing USD $1.78 million ($48.56 million present-day) in damages to the city and ripping spans from the High Bridge. In the 1960s, during urban renewal, Saint Paul razed western neighborhoods close to downtown. The city also contended with the creation of the interstate freeway system in a fully built landscape. From 1959 to 1961, the western Rondo Neighborhood was demolished by the construction of Interstate 94, which brought attention to racial segregation and unequal housing in northern cities. The annual Rondo Days celebration commemorates the African American community.
Downtown had short skyscraper-building booms beginning in the 1970s. The tallest buildings, such as Galtier Plaza (Jackson and Sibley Towers), The Pointe of Saint Paul condominiums, and the city's tallest building, Wells Fargo Place (formerly Minnesota World Trade Center), were constructed in the late 1980s. In the 1990s and 2000s, the tradition of bringing new immigrant groups to the city continued. As of 2004, nearly 10% of the city's population were recent Hmong immigrants from Vietnam, Laos, Cambodia, Thailand, and Myanmar. Saint Paul is the location of the Hmong Archives.