Kuechenberg was drafted by the Philadelphia Eagles as a fourth-round pick in the 1969 NFL Draft. He quit shortly after training camp started and played a season of semi-pro football with the Chicago Owls in the Continental Football League. Kuechenberg signed with the Dolphins as a free agent in 1970. He became a starter that season as the Dolphins finished 10–4 and made the playoffs for the first time in club history. The next season, 1971, helped the Dolphins make it to the Super Bowl, where they lost to the Dallas Cowboys 24–3. In that game Kuechenberg's opponent was Hall of Famer Bob Lilly.
The next two seasons the Dolphins won the Super Bowl (going 17–0 in 1972) and his play was noticed by New York Post writer Paul Zimmerman who named Keuchenberg on his All-pro ballot. The following season, 1974, was named All-AFC by Pro Football Weekly and was named to his first Pro Bowl. He was named 1st team All-Pro in 1975 and in 1978 and was named All-AFC three times. He was Second-team All-Pro in 1977.
Kuechenberg has also been critical of his former teams. One such critique prompted then-current Miami All-Pro, Jason Taylor, to comment, "It's another chapter in the grumpy Kuechenberg story. It's Kuechenberg. He gets up every year and complains about something. If it ain't one thing, it's another. He needs a hug and a hobby. It's ridiculous."
Bob Kuechenberg was inducted into the American Football Association's Semi Pro Football Hall of Fame in 1986. In 2013, President Barack Obama honored the entire 1972 Perfect Season Dolphins at an event in the White House, but Kuechenberg declined to attend for political reasons. He told sports columnist Dave Hyde of Ft. Lauderdale'sSun-Sentinel "I want to be careful, because mom said if you have nothing good to say about someone, then don't say anything. I don't have anything good to say about someone."