Castellanos signed with World Championship Wrestling in 1996, anglicizing his name to "Psychosis." His debut pitted him against Konnan at Clash of the Champions XXXII. Through the early years, Psychosis would typically face other luchadores, frequently getting a midcard spot during pay-per-view events. He engaged in a feud with Último Dragón, first working as the fan favorite. He was later signed by Dragon's former manager Sonny Onoo, turning into a villain in the process. During the entire length of the feud, he was unable to defeat the Dragon. He then began teaming with La Parka under Onoo's tutelage. After Onoo dropped them in favor of Yuji Nagata, the team began to break up, with La Parka attacking Psychosis after the matches. He beat La Parka at Spring Stampede on April 19, 1998. In 1998, Psychosis joined Eddie Guerrero's Latino World Order (LWO) group, which consisted entirely of Mexican wrestlers. The group was disbanded by Ric Flair on the January 11 episode of "Nitro".