Orndorff a semnat cu World Wrestling Federation la sfârșitul anului 1983 și și-a făcut debutul în ianuarie 1984, avându-l ca manager pe „Rowdy” Roddy Piper. Piper l-a poreclit pe Paul Orndorff „Mr. Wonderful”, o poreclă pe care a folosit-o de atunci. Orndorff și-a făcut debutul în WWF împotriva lui Salvatore Bellomo în seara în care Hulk Hogan l-a învins pe Iron Sheik pentru titlul mondial WWF World Heavyweight și „Hulkamania s-a născut”, 23 ianuarie 1984 la Madison Square Garden. Orndorff a devenit unul dintre primii oameni care s-au luptat pentru titlul mondial, ajungând direct în main event la mai puțin de o lună de la debut. Hogan a dispus de challenger și a mers mai departe, în timp ce Orndorff a luptat cu diverși adversari, inclusiv cu campionul intercontinental Tito Santana. Când Piper l-a atacat pe Jimmy Snuka pe platoul de filmare al emisiunii Piper’s Pit, Orndorff (precum și Bob Orton, Jr.) l-a ajutat pe Rowdy One în luptele sale. Orndorff și Piper s-au confruntat deseori cu Snuka și „The Tonga Kid” în competiția de tag team.
Pe la sfârșitul anului 1984, agresiunea lui Roddy Piper asupra lui Cyndi Lauper (kayfabe) i-a adus pe Orndorff și Piper pe un curs de coliziune cu Hulk Hogan și Mr. T. Dușmănia lui Hogan cu Piper a însemnat, de asemenea, că Orndorff a fost împins din nou în tabloul evenimentelor principale; el l-a învins pe Tony Atlas la The War to Settle the Score și apoi a jucat un rol în evenimentul principal. Consecințele Războiului pentru stabilirea scorului au dus la crearea WrestleMania, cu Hogan și Mr. T (susținuți de Jimmy Snuka) înfruntându-i pe „Rowdy” Roddy Piper și Paul Orndorff în evenimentul principal. Intervenția lui Orton la sfârșitul meciului s-a întors împotriva lui Orton, care l-a lovit din greșeală pe Orndorff cu ghipsul de la braț, permițându-i lui Hogan să-l imobilizeze pe Orndorff și să câștige meciul pentru echipa sa. Dând vina pe Orndorff pentru această înfrângere, Piper și Orton l-au atacat pe acesta în primul episod al emisiunii Saturday Night’s Main Event. Mai târziu, în cursul serii, Orndorff a alergat în ring pentru a egala taberele când Piper și Orton se pregăteau să facă echipă dublă cu Hulk Hogan. El și-a consolidat statutul de babyface concediindu-l public pe managerul Bobby Heenan la scurt timp după aceea.
Orndorff și Hogan au început să facă echipă pentru a se certa cu Piper și Orton, înfruntându-i în competiții în echipă în toată țara. Disputa lui Orndorff cu Piper și Orton a continuat să facă ravagii în timp ce Hogan a început să își apere titlul împotriva altor pretendenți; Orndorff i-a înfruntat atât pe Orton cât și pe Piper în competiții individuale, de obicei fără un rezultat concludent. După ce l-a concediat pe Bobby Heenan ca manager, Creierul a pus o recompensă de 25.000 de dolari pe Orndorff, plătibilă oricui ar putea să-l rănească. Când nimeni nu a reușit, Heenan a mărit recompensa la 50.000 de dolari. Unul dintre primii oameni care a încercat să revendice noua primă, mai mare, a fost chiar Roddy Piper, dar meciurile lor au scăpat atât de mult de sub control încât Bruno Sammartino a fost desemnat ca arbitru special în speranța de a menține pacea. În loc să mențină pacea, Sammartino a devenit o țintă pentru Orton și Piper, ceea ce a dus la formarea unei echipe între Orndorff și Sammartino. Orndorff a făcut echipă cu o varietate de adversari în luptele sale cu Piper și Orton, inclusiv cu André the Giant. În februarie 1986, Bobby Heenan a folosit un meci între Hulk Hogan și Don Muraco ca o oportunitate pentru ca King Kong Bundy să-l atace pe Hogan, pregătind meciul lor de la WrestleMania 2. În timp ce Hogan s-a luptat cu Bundy, Orndorff s-a luptat cu Don Muraco într-un meci care s-a încheiat cu o dublă eliminare.
Fustrarea lui Orndorff a fost alimentată și mai mult de Adrian Adonis, care a profitat de fiecare ocazie pe care a avut-o pentru a-și bate joc de Orndorff (inclusiv referindu-se la el ca fiind „Hulk Jr.”), spunând că acesta s-a înmuiat de când făcea echipă cu Hogan. Adonis a continuat să-l enerveze pe Orndorff, mergând până într-acolo încât l-a provocat pe Paul Orndorff să demonstreze cât de apropiată era cu adevărat relația sa cu Hulk Hogan. În timpul unei convorbiri telefonice televizate cu Hulk Hogan, lui Orndorff i s-a spus că Hogan era prea ocupat cu antrenamentele pentru a veni la telefon, lucru care l-a enervat la culme pe Orndorff. Următoarea dată când Hogan și Orndorff au făcut echipă, împotriva celor de la Moondogs, Orndorff a luptat singur cea mai mare parte a meciului în încercarea de a-l eclipsa pe Hogan, reușind să obțină pinul câștigător. Săptămâna următoare, în timpul unui meci în care Hogan și Orndorff s-au confruntat cu masivul duo format din Big John Studd și King Kong Bundy, Hogan și Orndorff s-au ciocnit accidental, iar Hogan l-a dat jos pe Orndorff de pe șezlong. Când Studd și Bundy au început să facă echipă dublă cu Hogan, Orndorff nu l-a ajutat; părea să se fi rănit la ochi în urma coliziunii. Abia când Studd și Bundy l-au pus pe Hogan într-o poziție compromisă, Orndorff a reintrat în ring pentru a-i respinge pe Studd și Bundy. Orndorff l-a ajutat apoi pe Hogan să se ridice în picioare, a ridicat mâna în aer și i-a aplicat lui Hogan o clothesline urmată de un piledriver.
Orndorff s-a reunit curând cu managerul Bobby Heenan și s-a luptat din nou cu Hulk Hogan, inclusiv un meci memorabil în aer liber la Toronto, care a atras aproximativ 76.000 de fani. După o serie de meciuri fără un rezultat curat, s-a decis ca Hogan și Orndorff să se confrunte într-un meci în cușcă de oțel în emisiunea Saturday Night’s Main Event. În meciul din cușcă, atât Orndorff, cât și Hogan s-au cățărat pe partea de sus a cuștii și au atins podeaua în același timp. După ce s-au revăzut imaginile, s-a decis că a fost o remiză și meciul a fost reluat. După ce meciul a fost reluat, Hogan a ieșit cu ușurință din cușcă și a câștigat meciul după o cădere a piciorului, punând capăt disputei dintre ei. Feuda lor, care a durat jumătate de an, este una dintre cele mai notabile (și profitabile) feude din istoria wrestlingului profesionist.
În timpul feudei cu Hogan, Orndorff s-a rănit grav la brațul drept într-un accident de haltere. Pentru că se afla în toiul luptei cu Hogan, care îi aducea mulți bani, nu a vrut să își ia timp liber pentru a se opera pentru a o trata corespunzător, alegând în schimb să continue să lupte. După ce programul cu Hogan s-a încheiat, Orndorff a avut un program redus timp de câteva luni, înainte de a fi nevoit să își ia o pauză din cauza accidentării. În timp ce Orndorff era departe de WWF, Bobby Heenan a adus un om nou, „Ravishing” Rick Rude, pentru a-i lua locul lui Orndorff în familia Heenan. Orndorff a revenit în ring special pentru a-l concedia pe Bobby Heenan și pentru a se dușmăni cu Rick Rude. Orndorff l-a luat ca manager pe Oliver Humperdink în lupta sa cu Rude și Heenan. Ultima apariție „mare” a lui Orndorff a fost la ediția inaugurală Survivor Series din 26 noiembrie 1987, unde a făcut echipă cu Hulk Hogan, Bam Bam Bigelow, Ken Patera și Don Muraco pentru a-i înfrunta pe Andre the Giant, One Man Gang, King Kong Bundy, Rick Rude și Butch Reed. La începutul meciului, Rude l-a eliminat pe Orndorff cu un roll-up.
Ca urmare a accidentării la haltere și a faptului că Orndorff nu s-a operat niciodată pentru a corecta accidentarea, brațul său drept este vizibil mai mic și mai puțin musculos decât cel stâng.
Paul Orndorff s-a retras la începutul anului 1988 din cauza accidentării la braț și s-a concentrat pe administrarea pistei sale de bowling din Fayetteville. În timpul cât a stat departe de acest sport, a fost de fapt raportat că ar fi murit; povestea a ajuns în mai multe ziare. Timpul de retragere a fost din cauza rănii la braț/gât pe care a suferit-o în timpul duelului cu Hogan și pe care a lăsat-o netratată prea mult timp. Cu timpul liber, Orndorff și-a revenit și a început să se antreneze, refăcându-și fizicul care i-a adus în primul rând porecla de „Mr. Wonderful”. Singura diferență era că brațul său drept era vizibil mai mic și slăbit din cauza unei accidentări la gât care a provocat leziuni nervoase și, în cele din urmă, atrofierea bicepsului drept.
În 1990, Orndorff a revenit în cercul pătrat, luptând o serie de meciuri împotriva lui Kerry Von Erich în circuitul independent. În primăvara anului 1990, Orndorff a semnat cu World Championship Wrestling, debutând ca membru al unui grup numit „Dudes with Attitudes”, format din el însuși, Sting, Lex Luger, Junkyard Dog și The Steiner Brothers. The Dudes l-au susținut pe Sting în lupta acestuia cu cei Patru Călăreți. La Clash of the Champions XI Orndorff l-a învins pe Arn Anderson, iar la Great American Bash din 1990, Orndorff a făcut echipă cu Junkyard Dog și El Gigante pentru a-i învinge pe Arn Anderson, Barry Windham și Sid Vicious prin descalificare. Orndorff a rămas la WCW până în toamna anului 1990.
Orndorff a revenit la WCW la sfârșitul anului 1992. În ianuarie 1993 l-a înfruntat pe Cactus Jack, învingătorul fiind ales de managerul Harley Race ca înlocuitor al lui Rick Rude, rănit, la Clash of the Champions. Race l-a asistat pe Orndorff în meci și i s-a alăturat rapid Vader în atacul său asupra lui Cactus Jack. După meci, Race a declarat că Paul Orndorff a fost alesul său. Orndorff a fost învins de Cactus Jack într-un meci Thunderdome ulterior; cei doi au avut o dispută intensă intensă, inclusiv un meci Falls Count Anywhere la SuperBrawl III, pe care Cactus Jack l-a câștigat.
După ce disputa cu Cactus s-a răcit, „Mr. Wonderful” a pus ochii pe titlul vacant de campion mondial de televiziune WCW. Orndorff s-a înscris la un turneu de 16 oameni, învingându-i pe 2 Cold Scorpio, Cactus Jack, Johnny B. Badd și apoi pe Erik Watts în finală pentru a câștiga primul său titlu WCW. Orndorff, campionul TV, și Rick Rude, campionul SUA, au început să facă echipă în mod regulat, inclusiv o victorie în PPV împotriva lui Dustin Rhodes și Kensuke Sasaki la Slamboree. În această perioadă, Orndorff a respins, de asemenea, provocările, printre alții, ale lui Ron Simmons și Marcus Alexander Bagwell, menținându-și titlul de televiziune prin orice mijloace necesare. Orndorff l-a învins pe Bagwell în mod controversat, folosindu-se de a doua coardă pentru a face pârghie în timpul imobilizării. Cei doi aveau să se dueleze mai târziu pentru titlul mondial WCW World Tag Team. Domnia lui Orndorff la titlul mondial de televiziune a inclus și o înfrângere prin descalificare în fața lui Johnny B Badd, după ce Maxx Payne a intervenit violent. Acest lucru a dus la o scurtă alianță în echipă de șase oameni între Orndorff, Payne și Chris Benoit. Pe 18 august 1993, norocul lui Orndorff s-a terminat, Ricky Steamboat câștigând titlul la Clash of the Champions XXIV. După ce l-a provocat fără succes pe Ricky Steamboat pe tot parcursul toamnei și iernii lui 1993, era timpul pentru o schimbare de ritm.
După ce Orndorff s-a retras, a început să conducă WCW Power Plant, unde a antrenat mai mulți luptători, inclusiv pe Natural Born Thrillers. El a avut un scurt rol pe ecran în această perioadă în Old Age Outlaws cu Terry Funk, Arn Anderson și Larry Zbyszko pentru a se duela cu ultima încarnare WCW a nWo.
La 3 februarie 2005, Orndorff a fost anunțat ca fiind unul dintre cei incluși în clasa 2005 în WWE Hall of Fame. El a fost introdus pe 2 aprilie la Universal Amphitheatre din Los Angeles, California, de către Bobby „The Brain” Heenan. Mai târziu, în cursul serii, în timpul prezentării lui Hulk Hogan, Orndorff a fost văzut clar că nu a aplaudat când Hogan a urcat pe scenă.
.