Malenko made his WCW pay-per-view debut at Halloween Havoc 1995 on October 29 in Detroit, MI. He, along with Chris Benoit, defeated the team of Steven Regal and Bobby Eaton. In January of the following year, in a singles contest, Alex Wright proved to be the next victim for Malenko.

On May 2, 1996, Malenko got his first taste of WCW gold by defeating Sinijiro Otani in Lake Buena Vista, FL. Just 17 days after becoming the first American to win the Cruiserweight title, Malenko defended the title at Slamboree 1996. In just under 10 minutes, Malenko defeated Brad Armstrong to remain the WCW Cruiserweight champion. Malenko went on to successful title defenses against Rey Mysterio, Jr. and Disco Inferno at The Great American Bash and Bash at the Beach, respectively.

Malenko at Hog Wild

On August 10, 1996 Malenko and Chris Benoit faced each other for the first time in WCW in Sturgis, SD at Hog Wild 1996. No winner was declared after the twenty-minute time limit, so the match went into double overtime. Early in the second period, Malenko fell victim to a suplex courtesy of Benoit but fought back to lock Benoit in the Texas Cloverleaf. However, Benoit�s valet, Woman, caused a distraction that enabled Benoit to gain the victory with a cradle at the 27:00 minute mark.

In a Cuiserweight title contest, Malenko fought Rey Mysterio, Jr. at Clash of the Champions XXXIII (August 15, 1996) in Denver, CO. This match was highlighted by a somersault into a senton splash by Mysterio and a fireman�s carry off the top rope into a gutbuster over the knee by Malenko. Malenko thought he had the victory in hand when referee Randy Anderson counted to three, but Anderson quickly re-started the match after realizing Mysterio had his leg on the rope. In the end, Mysterio came out on top after a springboard to retain the Cruiserweight title.

After not being on the Fall Brawl 1996 pay-per-view, Malenko returned at Halloween Havoc on October 27 in a big way. At the MGM Grand in Las Vegas, NV, Malenko became a two-time holder of the WCW Cruiserweight title by defeating Rey Mysterio, Jr. The following month at World War III on November 24, Malenko gained the victory over Psychosis and later was a part of the three-ring battle royal. At Starrcade 1996, in a nearly 20-minte match filled with a bevy of offense by both men, the Ultimo Dragon was able to secure the victory over Malenko and nab the Cruiserweight title that Malenko had held since Halloween Havoc. It should be noted that Sonny Onoo, the manager of Ultimo Dragon did play a role in allowing his man to win the contest.

Malenko

Malenko got his revenge the following month at Clash of the Champions XXXIV in Milwaukee, WI. The match that �was everything scientific strategists could have wanted,� ended with Malenko nailing a powerbomb on to Ultimo Dragon and winning back the Cruiserweight title for the third time. At SuperBrawl VII on February 23, 1997, Dean Malenko put up the Cruiserweight title against Syxx. Malenko had the early advantage, but Syxx fired back with his martial arts expertise. About halfway through the match, Syxx went for a sleep hold, but it was countered by Malenko, who went for a successful side suplex. Malenko then fell victim to a brainbuster and flying legdrop off of the top rope by Syxx. Syxx then went to use the title that was up for grabs, when Eddie Guerrero ran from the backstage area to steal the belt away from Syxx, apparently to aid Malenko. Around the 12-minute mark of the match, Guerrero then went on to �accidentally� crush Malenko with the Cruiserweight gold allowing Syxx to pick up the victory and to become the new Cruiserweight champion.

The following month at Uncensored in North Charleston, SC, Guerrero and Malenko, longtime rivals since their days in ECW, met up in the ring. The match had action both in and outside of the ring. Towards the end, Malenko actually landed a frogsplash on Guerrero, who is well known for using the frogsplash. Malenko did not go for the pin, but instead went to punish Guerrero some more. However, Guerrero got the upper hand by countering with a head-scissor takeover and a DDT from the ropes, eventually getting Malenko into the Texas Cloverleaf. At this point, Syxx ran down to ringside with a video camera, which Malenko used to defeat Eddie Guerrero. With the victory, Malenko also secured the United States championship.

Chris Benoit and the U.S. Champion, Malenko, wrestled to a no-contest at the Spring Stampede pay-per-view on April 6, 1997. The following month at Slamboree 1997, Dean Malenko wrestled Jeff Jarrett in a match that saw plenty of scientific wrestling maneuvers. For a great portion of the match, Dean Malenko worked on the legs of Jarrett to soften him up for the Texas Cloverleaf. Malenko remained undistracted by Debra and Steve McMicheal at ringside and secured the Texas Cloverleaf and the victory over Jarrett to remain the U.S. Champion. Malenko did finally lose the U.S. title to Jeff Jarrett on June 9, 1997 after interference by Eddie Guerrero.

After sitting out the June and July pay-per-views, Malenko returned at Road Wild on August 9, 1997. Malenko teamed with his last pay-per-view opponent, Jeff Jarrett to take on the team of Steve McMicheal and Chris Benoit in a tag team elimination match. Jarrett turned out to not be the partner he said he would be for Malenko. After tagging out before the minute-mark in the match, Jarrett did not re-enter the match for over 6 minutes. The forced Malenko to take the brunt of the punishment dished out by Benoit and McMichael including a powerslam by McMichael and a crisp snap suplex by Benoit. When Jarrett finally did tag back in, he laid down for McMichael leaving Malenko to fend for himself. After two more minutes of punishment that included a tombstone piledriver by both opponents, Malenko was pinned. Jarrett�s actions led to he and Malenko meeting up at Fall Brawl 1997. At the 9-minute mark of the match, Malenko nailed a top rope superplex and went for the Texas Cloverleaf, but Jarrett was able to reach the ropes, which forced Malenko to release the hold. Five minutes later, Jarrett gained the submission victory after Malenko submitted to the pain of the figure four.

On November 23, 1997, Dean Malenko was the 47th participant in the 60-man, 3-ring battle royal. Malenko ended the year at Starrcade against his bitter rival, Eddie Guerrero in a match for the Cruiserweight title. Malenko had the advantage early on unto Guerrero started working on the leg of Malenko. After countering the Cloverleaf, Guerrero landed a dropkick on Malenko�s already injured leg and went for the frogsplash to retain the Cruiserweight title.

At Souled Out in 1998, during the Raven vs. Chris Benoit match, Malenko make the save for Benoit after Raven�s Flock was about to attack Benoit. Before leaving the ring, the two men exchanged a look of mutual respect.

Malenko as Ciclope

Malenko and Chris Jericho, the self-proclaimed �Man of 1,004 Holds, wrestled Uncensored in Boston, MA. Jericho had the advantage for most of the match and ended up getting Malenko into the LionTamer. Malenko tried to make it to the ropes, but eventually had to submit to the pain. Following the match, Gene Okerlund approached Malenko about what he was going to do now that he lost and Malenko simply replied, �Home.� Malenko later stated about leaving WCW for a couple of months, �I needed to get back to my roots, my family life. That comes first in life, not just for wrestlers but for anybody. I needed family and friends around me to give me support and help bring me back to wrestling in a way I wanted to come back.� After listening to Jericho berate his legendary father, Boris Malenko, Malenko returned at Slamboree in May of 1998. Disguised as Ciclope, Malenko won a battle royal early in the pay-per-view to earn a title shot against Chris Jericho. Malenko came back with vengeance and secured the Texas Cloverleaf on Jericho to win the Cruiserweight title for the fourth time. After the match, Malenko looked up with belt in hand and stated, �Dad, this one�s for you.�

The Cruiserweight title was later vacated due to Jericho�s �Conspiracy Theory,� which led to Malenko and Jericho fighting each other at the Great American Bash the following month. After both men applied their finishing maneuvers on each other and both got out of them, Jericho screamed to Malenko, �You�re nothing, just like your dead father!� Those few words lit a fire in Malenko, who got disqualified for his relentless attack on Jericho. Security was eventually called in to restrain an infuriated Malenko.

At the Road Wild pay-per-view in August, Dean Malenko was the guest referee for a Cruiserweight title match involving Chris Jericho and Juventud Guerrera. Malenko remained impartial throughout the match, but decked Jericho afterwards.

On September 13, 1998 at Fall Brawl, Malenko met Curt Hennig in a grudge match. This occurred as result of Hennig crushing Malenko�s head with the door of a steel cage on Nitro. Malenko took home the victory by disqualification after the late Rick Rude interfered on the part of Hennig. Arn Anderson made the save for Malenko, but ended up on the receiving end of a beating as well. This spelled the beginning of the reformation of the Four Horsemen.

The following night, in Greenville, SC, Dean Malenko was announced as a new member of the Four Horsemen, along with Chris Benoit, Steve McMichael, Arn Anderson, and Ric Flair.

In November, Malenko and fellow Horsemen member Chris Benoit were two of the last ten men in the 60-man, 3-ring battle royal at World War III 1998. At SuperBrawl IX, Malenko teamed with Chris Benoit to take on Barry Windham and Curt Hennig. The two teams fought twice with the latter team eventually walking out the Tag Team Champions. The following month, Malenko and Benoit got revenge by defeating Hennig and Windham to become the Tag Team Champions for the first time together in WCW. Benoit later said of working with Malenko, �I�ve known Dean Malenko for 10 years. There�s obviously a lot of trust there. I�ve wrestled with him in Japan and Australia. We have a lot of confidence when we step into the ring together. I know he�ll be there if I�m in trouble, and he knows the same thing.�

The duo lost the titles on the March 29 edition of Monday Nitro. Malenko and Benoit (with Arn Anderson) beat Raven and Saturn at Spring Stampede in April 1999, as Malenko pinned Raven. At Slamboree 1999 emanating from St. Louis, Missouri, Malenko and Benoit lost the Tag Team titles in a three-way dance after Raven (who teamed with Saturn) pinned Kidman (who teamed with Rey Mysterio, Jr.). In a little bit of controversy, Malenko had Saturn in the Texas Cloverleaf at the same time Raven scored the pin.

Malenko lost to David Flair at the Bash at the Beach in 1999 after Ric Flair hit Malenko over the back of the head with the U.S. title. Later, Malenko teamed with Saturn and Shane Douglas to defeat Barry Windham, Curt Hennig, and Bobby Duncum Jr. at Road Wild 1999.

Malenko as part of the Revolution

Malenko joined with Douglas and Saturn to form The Revolution. Chris Benoit later joined The Revolution, but soon left after Saturn and Douglas turned heel. The Revolution members, Malenko and Douglas, fought The First Family members, Hugh Morrus and Brian Knobs at Fall Brawl on September 12, 1999. Morrus eventually landed the No Laughing Matter moonsault for the victory. Before the pay-per-view in October, Malenko and Chris Benoit went a brief wrestling tour in Japan. They returned at Halloween Havoc, where Malenko double-crossed his Revolution teammate, Chris Benoit by clocking him with a chair to allow Rick Steiner to become the Television champion.

The remaining Revolution members Malenko, Saturn, and Asya took on Filthy Animal members Eddie Guerrero, Kidman, and Torrie at Mayhem. Malenko got eliminated early, but The Revolution was still victorious after Saturn pinned Torrie. Malenko showed up later in the evening disguised to interfere in Benoit�s match with Bret Hart.

In what would be his last match for WCW, Malenko fought Kidman in a match where the loser would be the first one to touch the floor. Kidman gained the early advantage, and early in the match, Malenko went outside to lose the match.

Unhappiness in WCW and displeasure with changes in WCW officials prompted Malenko along with Benoit, Saturn, and Guerrero to ask for their releases from WCW. The four men were granted their releases and soon appeared in the World Wrestling Federation.