It had one airplane, a Piper Cub purchased for $1,300, and it was used to shuttle employees of the Blandin Paper Mill Company from Grand Rapids, Minnesota to Minneapolis. In 1950 Newstrom moved the company to Grand Rapids. In 1970, the Halverson family of Duluth, Minnesota bought Mesaba from Newstrom. On 4 February 1973, they started regularly scheduled airline services serving rural Minnesota communities. 

The Swenson family of Thief River Falls, Minnesota purchased Mesaba Aviation in 1977. They took the company public in 1982 as the airline began flying to Iowa, North Dakota and South Dakota, using a fleet of Beech 99s. In 1983, Mesaba became a codeshare partner of Republic Airlines, flying turboprop aircraft from small regional communities to the Minneapolis-Saint Paul International Airport. In 1986, after the merger of Republic Airlines and Northwest Orient Airlines, Mesaba transitioned their codeshare partnership, and began operations as a Northwest Airlink carrier. 

Mesaba began feeder service from Detroit Metropolitan Wayne County Airport to small airports across the east and midwest using Fokker F27 and Fairchild Metro aircraft in 1988. Maintenance bases were established both in Detroit and Wausau, Wisconsin. In 1991, Mesaba began adding the first of 25 De Havilland Canada Dash 8 aircraft (leased from Northwest Airlines) to begin replacing the Fokker F-27's. In 1995, Mesaba and Northwest reached an agreement to provide service with Saab 340 turboprop aircraft.