Randle went undrafted; he tried out for his brother's team, the Tampa Bay Buccaneers, but was thought to be too small, and was not signed to a contract. The 6'1" 287-lbs. defensive linemen was picked up by the Vikings after the draft on the recommendation by Head Scout Don Deisch, playing his first season in 1990. He went to his first Pro Bowl in 1993 after recording 11.5 sacks, and was quickly becoming one of the dominant defensive tackles of his era. Once Henry Thomas left the Vikings, Randle increased his training regimen, and became well known for his disarming on-field heckling of opposing players. Randle would record double digit sacks during nine different seasons, including a career-high and league-leading 15.5 sacks in 1997.
Randle had an ongoing rivalry with PackersquarterbackBrett Favre, whom he sacked more than any other quarterback; Favre said that Randle was the toughest defensive player he faced and "on artificial turf he's unblockable". To play off the rivalry with Brett Favre, Randle starred in a commercial which featured himself sewing a miniature version of Favre's #4 jersey which he put on a live chicken. The commercial then showed Randle chasing the chicken around what was supposed to be Randle's backyard and ended with Randle cooking chicken on his BBQ, leading to fierce protests from People for the Ethical Treatment of Animals. Like fellow Minnesota Viking Chris Hovan, Randle was known for eccentric face painting as well as trash talking on the field.
At the end of the 2000 season, Randle signed with the Seattle Seahawks, and retired in March 2004. He had planned to retire a year earlier, but Seahawks coach Mike Holmgren convinced him to stay one more year. The Seahawks made the playoffs in 2003 while he was on the roster, but did not reach the Super Bowl. Also that year while with the Seahawks, Randle acquired his final sack. Randle left the NFL tied with Richard Dent for 5th in number of career sacks, and his 137.5 career sacks is the most by a defensive tackle in NFL history, aside from Vikings legend Alan Page who had a total of 148.5 sacks. Over his career he was named to seven Pro Bowl squads. He was named All Tackle Machine of 1999 by Tackle: The Magazine.