1995, Flair began a short feud with Arn Anderson, which culminated in a tag match that saw Flair turning on Sting to reform the new Four Horsemen with Flair as the leader, Arn Anderson, Brian Pillman, and Chris Benoit as the members. With the new Four Horsemen, Flair won the WCW World Heavyweight Championship two more times before the nWo invasion storyline began in WCW, with the first one being in December 1995 at Starrcade, where Flair defeated Lex Luger and Sting by countout and then defeated Savage after all three Four Horsemen members ran to the ring and Arn Anderson knocked out Savage with brass knuckles, thus allowing Flair to pin Savage to win the match and the title. Afterwards Savage won the title back on Nitro after Starcade, but Flair won the next match at SuperBrawl VI to regain the championship. During the feud, Savage's manager Miss Elizabeth turned against him and became Flair's valet. Together with Woman and Debra McMichael they would escort Flair to his matches until Miss Elizabeth was taken by the nWo in the fall and eventually returned as Savage's valet when he joined the nWo in 1997. Flair lost the WCW World Heavyweight Championship eventually three months later to The Giant. The feud with Savage continued with The New Four Horseman joining the Dungeon of Doom to create an Alliance to end Hulkamania. Together the factions wrestled Hogan and Savage in a triple steel cage, End of Hulkamania match; losing to the reunited Mega Powers. Afterwards, Flair went on to win the WCW United States Heavyweight Championship and there were also changes in the Four Horseman in 1996, as Brian Pillman left WCW and Steve "Mongo" McMichael became the fourth member. Feud with the New World Order (1996–1999) Once again as a top fan favorite, Flair played a major role in the New World Order (nWo) invasion storyline in late 1996 and throughout 1997. He and the other Horsemen often took the lead in the war against Scott Hall, Kevin Nash, and Hollywood Hulk Hogan, whom Flair immediately challenged for the WCW World Heavyweight Championship at the Clash of the Champions XXXIII, but won only by disqualification. In September 1996, Flair and Anderson teamed with their bitter rivals, Sting and Lex Luger, to lose to the nWo (Hogan, Kevin Nash, Scott Hall, and an impostor Sting) in the WarGames match at Fall Brawl