Walls played high school football in Pontotoc, Mississippi. He spent his first three years as a quarterback at South Pontotoc High School. Before his senior year, he transferred to Pontotoc High School, a rival high school. Walls' transfer caused such an uproar in the area, the case went to court, and Walls' eligibility for baseball and basketball was denied. He switched to fullback his senior year, and made the all-state team.
Walls' ability at Pontotoc High earned him a scholarship to the University of Mississippi. He actually played defensive end for three years, but became a linebacker in his senior year. In addition, he played tight end. In a rare move under today's football system, Walls actually started both positions in a game against Memphis State University. After realizing that playing both offense and defense would be too much, he became the team's permanent tight end. He was still utilized on third-down situations as a pass rusher, however. He earned All-America honors as a senior. Walls was elected to the College Football Hall of Fame in 2014.
Walls was drafted in the second round (56th overall) by the San Francisco 49ers in the 1989 NFL Draft. Despite early success in his career, including catching a nine-yard pass in the 49ers 55-10 rout of the Denver Broncos in Super Bowl XXIV, he was second on the depth chart behind All-Pro Brent Jones. He spent the entire 1992 NFL season and 1993 NFL season on injured reserve because of nagging shoulder injuries. In 1994, he signed as a free agent with the New Orleans Saints. Walls spent two seasons with the Saints, setting the team record for tight end receptions in 1995 with 57. He then signed a deal with the Carolina Panthers to become their starting tight end. It was in Carolina that Walls finally broke out as a player. He made the Pro Bowl five times between 1996 and 2001, only missing it during the 2000 season due to injuries that kept him out for 8 games. While at Carolina, he was also the back-up punter to Ken Walter. After Carolina declined to re-sign him in 2003, he signed with the Green Bay Packers, mostly backing up Bubba Franks, and retired the following year. Walls finished his career with 450 catches for 5,291 yards and 54 touchdowns. Upon his retirement, he was considered one of the premier tight ends in the game.