Sanders made his World Championship Wrestling debut on the October 10, 1998 episode of Saturday Night in a losing effort to Chavo Guerrero, Jr.. After being utilized as a jobber in a handful of matches on Saturday Night and WorldWide throughout 1998 and 1999, Sanders picked up his first victory on the July 19, 2000 episode of Thunder by defeating Crowbar. Sanders was introduced in mid-2000 as "Above Average" Mike Sanders.
On the August 16 episode of Thunder, Sanders was courted by Disco Inferno to join The Filthy Animals. After accompanying Rey Mysterio, Jr. and Juventud Guerrera for their tag team match against Sean O'Haire and Mark Jindrak, Sanders turned on the Animals and, along with Chuck Palumbo, Shawn Stasiak, and Reno, helped O'Haire and Jindrak attack the Animals and lose the match via disqualification in the process. On the August 21 episode of Nitro, the stable was named The Natural Born Thrillers, with Sanders serving as the stable's mouthpiece. After Sanders was interrupted during a promo by Filthy Animal member Konnan, the Thrillers (Sanders, Jindrak, and O'Haire) subsequently defeated the Animals (Mysterio, Jr., Guerrera, and Disco Inferno) in a six-man tag team match.
The Thrillers continued their feud with the Animals, with Sanders defeating the Inferno on the August 23 episode of Thunder and the Thrillers defeating the Animals in an elimination match. On September 17 at Fall Brawl, the Thrillers faced the Animals, Big Vito and their mystery partner (later revealed to be Paul Orndorff) in an elimination match, which ended in a no-contest due to Orndorff suffering a stinger during the match. The Thrillers would then go on to lose a two-on-five handicap match against the Animals on the September 18 episode of Nitro despite having a numerical advantage, ending the feud between the two stables.
Following their feud with the Filthy Animals, the Natural Born Thrillers would go on to lose to The Jung Dragons on the September 20 episode of Thunder. After naming himself the new WCW Commissioner on the September 27 episode of Thunder, the Thrillers gained Kevin Nash as a "coach". With Nash, Sanders defeated then-Cruiserweight Champion Elix Skipper in a handicap powerbomb match orchestrated by Sanders on the October 2 episode of Nitro, resulting in Sanders becoming the new Cruiserweight Champion. He then went on to retain the Cruiserweight Title against Lance Storm in his first title defense on the October 4 episode of Thunder. Sanders then entered into a feud with Ernest Miller over the Commissionership, and defeated Miller in a kickboxing match at Halloween Havoc on October 29 to retain his position as Commissioner thanks to interference by Shane Douglas. The Thrillers then ended their alliance with Nash by attacking him during a title match against then-World Heavyweight Champion Booker T, after finding Nash no longer useful due to Sanders being the new Commissioner. The Thrillers then lost to Nash in a handicap match via disqualification on the November 12 episode of Nitro. On November 16 at the Millennium Final pay-per-view, Miller defeated Sanders to become the new WCW Commissioner. After retaining the Cruiserweight Title against Kwee Wee on November 26 at Mayhem, Sanders lost the title to Chavo Guerrero, Jr. on the December 6 episode of Thunder.
On the December 12 episode of Nitro, Sanders was squashed by Sid, though the Thrillers would manage to defeat The Insiders (Nash and Diamond Dallas Page) in a handicap match later in the night in what turned out to be the Thrillers' final match together.
At Sin on January 14, 2001, Sanders faced Miller in a rematch for the Commissionership, but was once again defeated. Following this, Sanders teamed with Kwee Wee and lost to the Jung Dragons in a first round match of a tournament to crown the inaugural Cruiserweight Tag Team Champions. On the final episode of Thunder on March 14, Sanders wrestled his final match for WCW as he and Disqo lost to Konnan and Hugh Morrus in a tag team match.
In late March 2001, the World Wrestling Federation bought out WCW. On June 24, 2002, Sanders wrestled his only match for the now-renamed World Wrestling Entertainment as he and Jason Sugarman defeated B.J. Payne and Steve Bradley in a tag team dark match before Sunday Night Heat. He was released from the company on July 19, 2002.