10 czerwca w WCW debiutował inny były zawodnik WWF, Kevin Nash, który pobił głównego zarządcę organizacji, Erica Bischoffa, poniżył werbalnie Stinga i Hulka Hogana oraz utworzył tag team The Outsiders ze Scottem Hallem.
7 lipca 1996 na gali Bash at the Beach miał miejsce pojedynek 3 na 3 między zawodnikami wiernymi organizacji a najeźdźcami. WCW reprezentowali Randy Savage, Lex Luger i Sting, a inwazję Scott Hall, Kevin Nash i zapowiedziana tajemnicza trzecia osoba, która nie pojawiła się w ringu na czas. We wczesnej fazie pojedynku Luger doznał kontuzji i odszedł za kulisy. Później w wejściu na arenę pojawił się Hulk Hogan. Powoli szedł w stronę ringu oklaskiwany przez publiczność. Niespodziewanie Hogan zaatakował Randy'ego Savage’a Leg Dropem. Widownia szybko zmieniła swoje nastawienie, bucząc i rzucając śmieci w stronę ringu. Po walce wygranej przez najeźdźców, Hogan zaczął obrażać zgromadzony tłum i ogłosił, że zakłada z Hallem i Nashem stajnię o nazwie New World Order. Hulk Hogan stał się heelem po raz pierwszy od 15 lat. Przyjął nowy pseudonim ringowy – Hollywood Hogan – i zaczął nosić czarny strój charakterystyczny dla swojej nowej drużyny.