 Explorers searching for the fabled Northwest Passage and large inland seas in North America continued to pass through the state . In 1721 , the French built Fort Beauharnois on Lake Pepin . In 1731 , the Grand Portage trail was first traversed by a European , Pierre La Vérendrye . He used a map written down on a piece of birch bark by <unk> , an Assiniboine guide . The North West Company , which traded in fur and competed with the Hudson 's Bay Company , was established along the Grand Portage in 1783 – 1784 . 
