Stenvig was born in Minneapolis in 1928. Growing up in South Minneapolis, he attended Roosevelt High School, where he won a Minnesota state high school boys' golf championship. Stenvig graduated from Augsburg College with a degree in sociology. He then joined the Minneapolis Police Department, working his way up to the rank of detective with the burglary squad, before entering Minneapolis politics.
In 1969, Stenvig entered the mayoral election as an independent candidate. DFL Mayor Arthur Naftalin had declined to run for a fifth term and the race for the open seat attracted several candidates. Stenvig ran an unconventional campaign that relied on limited funds and volunteer labor. After winning a three-way primary election, forcing out DFL candidate Gerard Hegstrom, he went on to defeat the Republican candidate, 7th Ward alderman and Council President Dan Cohen, in the general election. Stenvig received 62% of the vote in the election, surprising many veteran political observers in the city.[1] He was reelected in 1971, defeating DFL candidate W. Harry Davis by a wide margin. In the 1973 election, Stenvig lost to DFL candidate Albert Hofstede. He won back the mayor's office in a 1975 rematch with Hofstede, then lost to Hofstede again in 1977. In 1978, he lost the Republican primary for Minnesota secretary of state. In 1979, Stenvig ran again for mayor and lost to Donald M. Fraser. In 1982, he ran for Hennepin County sheriff and lost.
In 1981, Stenvig and members of his family appeared on an episode of the game show Family Feud, where they faced the Tuck family. The Stenvig family lost 422–0.
After retiring from the police department, Stenvig moved to Arizona in the late 1980s and died there on February 22, 2010.[2]