Randle non fu scelto nel Draft NFL 1990 e fece un provino con la squadra di suo fratello Earvin, i Tampa Bay Buccaneers, ma fu ritenuto di taglia non sufficiente. Disputò così il training camp dei Minnesota Vikings, i quali gli fecero firmare un contratto facendolo debuttare nella NFL nel 1990. Fu convocato per il suo primo Pro Bowl nel 1993 dopo aver fatto registrare 11,5 sack e diventando velocemente uno dei defensive tackle più dominanti della sua epoca. Randle andò in doppia cifra con i sack in otto diverse stagioni con i Vikings, con un primato in carriera di 15,5 nel 1997.
Randle ebbe la sua maggior rivalità col quarterback dei Green Bay PackersBrett Favre, il quale subì i suoi sack più di qualsiasi altro quarterback; Favre disse che Randle era il più difficile difensore che avesse mai incontrato e che "sul terreno artificiale era impossibile da fermare"[1]. Come il compagno di squadra ai Minnesota Vikings Chris Hovan, Randle era conosciuto per le sue pitture eccentriche del volto e per il suo linguaggio sporco in campo[2].
Alla fine della stagione 2000, Randle firmò coi Seattle Seahawks e si ritirò nel marzo 2004. Egli aveva pianificato di ritirarsi un anno prima, ma l'allenatore dei Seahawks Mike Holmgren lo convinse a disputare un ultimo anno. I Seahawks raggiunsero i playoff due volte con Rande nel roster, ma non riuscirono a raggiungere il Super Bowl. Questi lasciò la NFL alla pari con Richard Dent al quinto posto di tutti i tempi per sack in carriera e i suoi 137,5 sack totali sono il secondo miglior risultato della storia per un defensive tackle dopo la leggenda dei Vikings Alan Page con 148,5 sack[3].