On May 5, 2006, Kozlov had his first untelevised WWE match during a house show in San Jose, California, defeating Rob Conway. The next night, at another house show in Sacramento, California, Matt Striker cut a promo on Kozlov, calling him a "filthy immigrant", causing Kozlov to attack him. Kozlov then picked up the microphone and said he that he is "proud to be in America."
On the December 18, 2006 episode of Raw, Kozlov made an appearance as a WWE prospect. For the next several weeks, Kozlov was interviewed on WWE programming, proclaiming his love for "Double Double E" (WWE) but also began drawing a villainous response after declaring his superiority over whatever wrestlers were competing at the time, saying "I could beat both of them." He then was taken off television for over a year while participating in a number of dark matches, all of which he won.
On the April 4, 2008 episode of SmackDown, Kozlov made his official WWE debut as a villain, with the unique quirk of having no entrance music and no TitanTron video – his "entrance" consisted of complete darkness except for a solitary spotlight following him to the ring. He defeated Matt Bentley in his first match, and over the following weeks, Kozlov would go on to easily win several matches, first against local talent and then established names including Colin Delaney, Funaki, Nunzio, Shannon Moore, Jimmy Wang Yang, Jamie Noble, and Domino. On the July 11, 2008 episode of SmackDown, Kozlov debuted an entrance theme and TitanTron video as he defeated Stevie Richards.
In the following weeks, as Kozlov continued to easily win matches, he began demanding "better competition". On the September 12, 2008 episode of SmackDown, he started to seek that competition, attacking Jeff Hardy. Over the following weeks, Kozlov would continue attacking both Hardy and the WWE Champion Triple H, eventually starting a loose feud between the three of them over the WWE Championship. On the November 7 episode of SmackDown, Kozlov earned a match against Triple H for the WWE Title at Survivor Series after defeating The Undertaker by disqualification after he was attacked by Jeff Hardy. The match was originally intended to include Kozlov, Jeff Hardy, and Triple H, although Hardy was removed due to a storyline injury. The result of this was the addition of Edge to the match while it was in progress, and ultimately Edge would go on to pin Triple H and win the title.
Continuing his pursuit of the WWE Title, Kozlov competed in and was unsuccessful in winning a Beat The Clock Challenge Match against ECW Champion Matt Hardy for another title shot. This led to the two meeting at Armageddon, where Kozlov gained his first pay-per-view win by defeating Hardy in a non-title match. Kozlov competed in the 2009 Royal Rumble match, entering as the sixth participant but was eliminated by Triple H after eliminating The Great Khali, Carlito, and Montel Vontavious Porter. He then qualified to be part of the No Way Out Elimination Chamber match, where he was pinned for the first time after receiving a Last Ride from Undertaker, though he still remained unpinned in one-on-one competition. Kozlov's undefeated streak in televised singles competition ended on the March 2, 2009 episode of Raw, in which he was defeated by Shawn Michaels; this match was for the opportunity to face The Undertaker at WrestleMania XXV. His first televised singles loss on SmackDown came against The Undertaker on March 13, 2009.
On April 13, 2009, Kozlov was drafted to the ECW brand as part of the 2009 WWE Draft, as ECW's only pick of the night. Shortly after the draft, his character was tweaked to further highlight the training he received within the Russian military. He won his first match on the brand when he easily defeated a local competitor. On the June 30 episode of ECW on Syfy, he teamed with William Regal to defeat Christian and Tommy Dreamer. His first defeat in single's competition on ECW came on the July 9, 2009 episode of ECW, where he lost a number one contender's match to Christian for Tommy Dreamer's ECW Championship at Night of Champions.
On July 21, Kozlov began an angle with Ezekiel Jackson in which, week after week, after one of them had easily defeated a local competitor, the other would come out and hit their finishing move on the fallen opponent in a game of one-upmanship. On the August 18 episode of ECW, Jackson was set to team with ECW Champion Christian against the team of Kozlov and number-one contender William Regal. Jackson turned on Christian, forming an alliance with Regal and Kozlov. Kozlov and Jackson aided Regal in his feud with Christian over the ECW Championship, but Regal was unable to capture the title.
On the December 15 episode of ECW, Kozlov came out with Regal to face Jackson in an ECW Homecoming battle royal qualifying match. During the match, Regal turned on Kozlov by pulling his feet while at ringside, which ultimately cost him the match. After the match, Kozlov attempted to attack Regal, but Jackson jumped him from behind and both proceeded to attack Kozlov. This split Kozlov from the Ruthless Roundtable, making him a face character.
When the ECW brand came to an end, Kozlov, along with all other ECW talent, became a free agent. Kozlov would make his debut for the Raw brand on March 8, 2010 in a handicap gauntlet match with John Cena competing against Kozlov, Mr. McMahon, Drew McIntyre, Jack Swagger, and Mark Henry, reverting him to a heel. On the May 3 episode of Raw, he would team again with his former ECW partner William Regal to face the tag team champions The Hart Dynasty, Kozlov and Regal were defeated when Regal tapped out to David Hart Smith's Sharpshooter. On the May 10 episode of Raw, he appeared backstage with Santino Marella, William Regal, and Flavor Flav in a backstage segment, where Santino asked to join him in a tag team. However, Kozlov refused to join, stating that "he (Santino) always loses". The May 20th episode of Superstars, after Santino made another offer to form a tag team with him, Kozlov beat him in a squash match.
On the May 31st episode of Raw, Kozlov turned face again when he slammed Regal behind the referee's back during a mixed tag team match, allowing Santino Marella and Eve Torres to pick up the win. On the June 7 episode of Raw, he and Santino Marella were forced to compete in a dance-off, which Kozlov won. On June 14 episode of Raw, Kozlov served as a special referee for the match between William Regal and Santino Marella which Marella won after Kozlov intentionally gave him a fast count. On the June 28 episode of Raw, he fought Marella one on one with the stipulation being if Kozlov loses he would become Marella's tag team partner. He won, however, with Regal interfering after the match. Kozlov stopped Regal with a big boot to the chest and then carried Marella backstage. The following week, he teamed with Santino against William Regal and The Great Khali. Kozlov and Santino went on to win the match, while after the conclusion of the match, The Great Khali hit Regal with the brain chop. In the following weeks, Kozlov and Santino would continue their undefeated streak on both Raw and Superstars.
At Night of Champions 2010 Kozlov and Santino Marella competed in a tag team turmoil match for the WWE Tag Team Championship but were unsuccessful as the titles were won by "Dashing" Cody Rhodes and Drew McIntyre. On the November 15th episode of Raw, Kozlov and Marella fought in a tag team match against The Usos to determine the #1 contenders for the WWE Tag Team Championship. They won the match and faced the reigning Tag Team Champions Heath Slater and Justin Gabriel at Survivor Series, which they lost. They went on to win the Tag Team Championship in a Four-Way elimination tag team match on Raw on December 6, 2010 against The Usos, Slater and Gabriel and the tag team of Mark Henry and Yoshi Tatsu. At Tables, Ladders & Chairs, Kozlov and Marella defeated Slater and Gabriel by disqualification to retain the title. They would also enjoy successful title defenses over the likes of Chavo Guerrero and Drew McIntyre, The Usos, as well as The New Nexus (Husky Harris and Michael McGillicutty). The duo lost the Tag Team Titles back to Slater and Gabriel at Elimination Chamber. Kozlov was suppose to be apart of an 8 man tag match at WrestleMania 27 in Atlanta, GA. However, during a WWE Axxess match, he was attacked by The Corre members and Kofi Kingston would take his place at the event.
On March 8, Kozlov would then become the pro to Conor O'Brian on NXT Redemption. On March 22 of NXT Redemption, Kozlov and his rookie O'Brian beat JTG and his rookie Jacob Novak in a dance-off. Afterwards, Kozlov began teaching O'Brian sambo-like dancing and board breaking. O'Brian was eliminated on the June 28, 2011 episode of NXT, being the fourth rookie eliminated from the competition. Kozlov would then go on to feud with JTG on NXT, defeating JTG on three occasions. Kozlov's last match was on the August 5 episode of SmackDown, where he lost to Mark Henry and had his leg subsequently broken by Henry after the match. That same day, it was announced that Kozlov had been released from his WWE contract.