participants in the PRIDE 2004 Heavyweight Tournament, alongside teammate Mark Coleman. His first round match up at PRIDE Total Elimination 2004 was against former K-1 kickboxer Mirko Cro Cop, a participant heavily favored to win the entire tournament. Randleman knocked out Cro Cop by ground and pound following a left hook that surprised and knocked him down. In the second round, at PRIDE Critical Countdown 2004, Randleman faced off against the reigning PRIDE Heavyweight Champion Fedor Emelianenko. Again a heavy underdog, in a short bout he managed to suplex Fedor onto his head, landing in north-south position. This maneuver failed to damage Fedor, who quickly capitalized on Randleman's characteristic failure to inflict damage upon opponents from a dominant position by reversing him and submitting him with a kimura, thereby eliminating him from the tournament. With his tournament journey over, Randleman went on to square off against friend and fellow American wrestler Ron Waterman at PRIDE Final Conflict 2004. Randleman picked up and slammed much bigger Waterman, and was ahead on the scorecards but made one mistake and lost by americana in the first round. At PRIDE Shockwave 2004 Randleman offered a rematch to Mirko Cro Cop. Cro Cop submitted Randleman in the first round via guillotine choke, avenging his loss and adding another loss to Randleman's losing streak in the process. In the Opening Round of PRIDE's 2005 Middleweight Grand Prix, Kevin Randleman lost to Kazuhiro Nakamura via decision. In November 2005, Randleman appeared in Bushido Europe: Rotterdam Rumble, Europe's first Bushido event, and defeated Fatih Kocamis via decision, ending his losing streak, and giving him his first win in nearly a year. Randleman was taken ill with a serious fungal lung infection after his Rotterdam bout that had unknowingly been present for sometime. He underwent a successful surgery to have the infection removed. After recovering, he was scheduled to fight against Vitor Belfort at a Strikeforce event in San Jose, California on June 9, 2006, but was unable to, due to a recurrence of the infection. Belfort instead fought, and lost to, Alistair Overeem, by unanimous decision. Kevin Randleman returned to PRIDE for their first show on American soil, Pride 32: The Real Deal on October 21, 2006, where he was quickly submitted with a toe hold in the first round by 2005 Middleweight Grand Prix Champion Maurício "Shogun" Rua. This match-up was made partly to capitalize on an