Pre-wrestling
Prudius ha ottenuto numerosi successi, diventando il campione USA Open Heavyweight Sambo 2005 e il campione internazionale Heavyweight Grappling della United States Kick-Boxing Association (USKBA). Ha anche giocato a football americano per la squadra nazionale ucraina e per il Santa Barbara City College.
Total Nonstop Action Wrestling (2005)
Prudius ha accompagnato Jerry Jarrett sul ring a Slammiversary nel 2005.
World Wrestling Entertainment (2006-2011)
Il 17 gennaio 2006, la World Wrestling Entertainment annunciò che Prudius aveva firmato un contratto di sviluppo e fu mandato alla Deep South Wrestling. Il 7 aprile 2006 iniziò a lottare con il suo vero nome "Oleg Prudius" ed ebbe il suo primo match nella DSW contro Tommy Suede.
Il 5 maggio 2006, Prudius ebbe il suo primo match non trasmesso dalla WWE durante un house show a San Jose, California, sconfiggendo Rob Conway. La notte successiva, in un altro house show a Sacramento, California, Matt Striker tagliò un promo su Prudius, chiamandolo un "sporco immigrato", causando Prudius ad attaccarlo. Prudius prese poi il microfono e disse che è "orgoglioso di essere in America".
Nell'episodio di Raw del 18 dicembre 2006, Prudius fece un'apparizione come un futuro della WWE chiamato Vladimir Kozlov, che divenne il suo ring name. Per le prossime settimane, Kozlov è stato intervistato sulla programmazione WWE, proclamando il suo amore per "Double Double E" (WWE), ma disegnando un po' di calore heel per dichiarare la sua superiorità su qualsiasi wrestler erano in competizione in quel momento.
Ohio Valley Wrestling (2007-2008)
Il 28 luglio 2007 a Louisville, Kentucky, vinse l'OVW Heavyweight Championship sconfiggendo Paul Burchill, ma cedette il campionato la sera stessa a Michael W. Kruel a causa di un accordo che avevano fatto prima.
SmackDown (2008-2010)
Nella puntata di SmackDown del 4 aprile 2008, Kozlov fece il suo debutto ufficiale nella WWE come cattivo, con la particolarità di non avere nessuna musica d'ingresso e nessun video del TitanTron - la sua "entrata" consisteva nella completa oscurità tranne che per un riflettore che lo seguiva sul ring. Sconfisse Matt Bentley nel suo primo match, e nelle settimane successive, Kozlov avrebbe vinto una serie di incontri. Nella puntata di SmackDown dell'11 luglio 2008, Kozlov debuttò con un tema d'ingresso e un video TitanTron mentre sconfiggeva Stevie Richards.
Nelle settimane successive, mentre Kozlov continuava a vincere facilmente gli incontri, iniziò a chiedere una "concorrenza migliore". Nell'edizione di SmackDown del 12 settembre 2008, attaccò Jeff Hardy. Nelle settimane successive, Kozlov avrebbe continuato ad attaccare sia Hardy che il WWE Champion Triple H, iniziando alla fine una rivalità allentata tra loro tre per il titolo WWE. Kozlov si guadagnò un match contro Triple H per il WWE Championship a Survivor Series sconfiggendo The Undertaker per squalifica nella puntata di SmackDown del 6 novembre. Edge fu aggiunto al match mentre era in corso, e bloccò Triple H per vincere il match. Questo perché Jeff Hardy avrebbe dovuto originariamente gareggiare, ma fu trovato privo di sensi nella tromba delle scale di Boston. Ad Armageddon, Kozlov ottenne la sua prima vittoria in pay-per-view sconfiggendo l'allora ECW Champion Matt Hardy in un non-title match. Kozlov partecipò al Royal Rumble match del 2009, entrando al numero 6, ma fu eliminato da Triple H dopo aver eliminato altre tre superstar tra cui The Great Khali, MVP e Carlito.
