's first contestation for the Senate of the United States was in 1958. He ran in the 1958 elections against incumbent Republican Senator Frederick G. Payne. Muskie won the election with 60% of the vote against Payne's 39%. He was one of the 12 Democrats who overtook Republican incumbents and established the party as the party-of-house during the election cycle. "The New York Times" reported that during this election that the absentee ballots requested for Democrats increased considerable signaling voter-discontent with Republican ideology. This election was considered the largest single-party gain in the Senate's history.