Kastenmeier made an unsuccessful bid for Congress in Wisconsin's 2nd congressional district in 1956, losing to Republican Donald Tewes by 11 points. In a rematch in 1958 he defeated Tewes by 6,200 votes, and became the first Democrat to hold the seat in 28 years. He won a third race with Tewes in 1960, and faced another close contest in 1962. However, he romped to a fourth term in 1964 and was re-elected with comfortable majorities twelve more times over the next 24 years, serving from the 86th United States Congress to the 101st.