After impressing higher-ups with his work, he was approached by Ric Flair and the WCW booking staff to become a member of the reformed Four Horsemen in 1995, alongside Flair, Arn Anderson, and Brian Pillman; he was introduced by Pillman as a gruff, no-nonsense heel similar to his ECW persona, "The Crippler". He was brought in to add a new dynamic for Anderson and Flair's tormenting of Hulk Hogan and Randy Savage in their "Alliance to End Hulkamania", which saw the Horsemen team up with The Dungeon of Doom, but that alliance ended with Dungeon leader and WCW booker, Kevin Sullivan feuding with Pillman. When Pillman abruptly left the company for the WWF, Benoit was placed into his ongoing feud with Sullivan. This came to fruition through a dissension between the two in a tag team match with the two reluctantly teaming with each other against The Public Enemy, and Benoit being attacked by Sullivan at Slamboree. This led to the two having violent confrontations at pay-per-views, which led to Sullivan booking a feud in which Benoit was having an affair with Sullivan's real life wife and onscreen valet, Nancy (also known as Woman). Benoit and Nancy were forced to spend time together to make the affair look real, (hold hands in public, share hotel rooms, etc.).