While Klecko has been nominated for the Pro Football Hall of Fame several times, he has not been enshrined. Hall of Fame center Dwight Stephenson, in describing Klecko as a "great defensive lineman", considered him one of the two best interior linemen he had ever faced. Hall of Fame tackle Anthony Muñoz said about Klecko, "In my 13 seasons, Joe is right there at the top of the defensive ends I had to block, up there with Fred Dean, Lee Roy Selmon and Bruce Smith. Joe was the strongest guy I ever faced. He had perfect technique — hands in tight, great leverage. My second year, 1981, we went to Shea and beat the Jets, 31–30, but he was such an intense, smart player, I knew I was in a battle. He was the leader, the guy who kept that unit together."