Orndorff skrev på för World Wrestling Federation i slutet av 1983 och debuterade i januari 1984 med ”Rowdy” Roddy Piper som manager. Piper gav Paul Orndorff smeknamnet ”Mr Wonderful”, ett smeknamn som han har använt sedan dess. Orndorff gjorde sin WWF-debut mot Salvatore Bellomo samma kväll som Hulk Hogan besegrade The Iron Sheik för WWF:s världstungviktstitel och ”Hulkamania föddes”, den 23 januari 1984 i Madison Square Garden. Orndorff blev en av de första som utmanade om världsmästartiteln och sköt sig direkt in i huvudmatchen mindre än en månad efter sin debut. Hogan gjorde sig av med utmanaren och gick vidare medan Orndorff slogs mot en rad olika motståndare, bland annat mot den interkontinentala mästaren Tito Santana. När Piper attackerade Jimmy Snuka på inspelningen av Piper’s Pit hjälpte Orndorff (liksom Bob Orton, Jr.) Rowdy One i hans slagsmål. Orndorff och Piper mötte ofta Snuka och ”The Tonga Kid” i tag team-tävlingar.
Närmast i slutet av 1984 förde Roddy Pipers misshandel av Cyndi Lauper (kayfabe) Orndorff och Piper på kollisionskurs med Hulk Hogan och Mr. T. Hogans fejd med Piper innebar också att Orndorff återigen blev en del av huvudmatchen; han besegrade Tony Atlas på The War to Settle the Score och spelade sedan en roll i huvudmatchen. Nedfallet från The War to Settle the Score ledde till skapandet av WrestleMania, där Hogan och Mr T (med stöd av Jimmy Snuka) mötte ”Rowdy” Roddy Piper och Paul Orndorff i huvudmatchen. Ortons inblandning i slutet av matchen slog tillbaka när han råkade slå Orndorff med gipset på hans arm, vilket gjorde att Hogan kunde sätta fast Orndorff och vinna matchen för sitt lag. Piper och Orton gav Orndorff skulden för förlusten och attackerade honom i det första avsnittet av Saturday Night’s Main Event. Senare under kvällen sprang Orndorff till ringen för att jämna ut sidorna när Piper och Orton förberedde sig för att dubbelteam Hulk Hogan. Han befäste sin babyface-status genom att offentligt avskeda managern Bobby Heenan kort därefter.
Orndorff och Hogan började slå sig samman i fejd med Piper och Orton och mötte dem i tag team-tävlingar över hela landet. Orndorffs fejd med Piper och Orton fortsatte att rasa medan Hogan började försvara sin titel mot andra utmanare; Orndorff mötte både Orton och Piper i individuella tävlingar, oftast utan avgörande resultat. Efter att ha sparkat Bobby Heenan som hans manager satte Brain ett pris på Orndorff på 25 000 dollar, som kunde betalas ut till den som kunde skada honom. När ingen lyckades höjde Heenan bountyn till 50 000 dollar. En av de första männen som försökte göra anspråk på den nya, högre bonusen var Roddy Piper själv, men deras matcher gick så mycket överstyr att Bruno Sammartino utsågs till specialdomare i hopp om att bevara freden. Istället för att hålla fred blev Sammartino en måltavla för Orton och Piper, vilket ledde till att Orndorff och Sammartino slog sig ihop. Orndorff samarbetade med en mängd olika motståndare i sina matcher med Piper och Orton, bland annat André the Giant. I februari 1986 använde Bobby Heenan en match mellan Hulk Hogan och Don Muraco som ett tillfälle att låta King Kong Bundy attackera Hogan, vilket satte igång deras match på WrestleMania 2. Medan Hogan kämpade mot Bundy kämpade Orndorff mot Don Muraco i en match som slutade med dubbel nedräkning.
Orndorffs frustrationer underblåstes ytterligare av Adrian Adonis, som tog varje tillfälle som han kunde för att håna Orndorff (bland annat genom att referera till honom som ”Hulk Jr”), och sa att han hade blivit mjuk efter att ha samarbetat med Hogan. Adonis fortsatte att irritera Orndorff och gick till och med så långt att han utmanade Paul Orndorff att bevisa hur nära hans relation med Hulk Hogan egentligen var. Under ett tv-sänt telefonsamtal med Hulk Hogan fick Orndorff veta att Hogan var för upptagen med att träna för att komma till telefonen, något som irriterade Orndorff till det yttersta. Nästa gång Hogan och Orndorff samarbetade, mot Moondogs, brottade Orndorff större delen av matchen på egen hand i ett försök att sätta Hogan i skymundan, och gjorde den vinnande nålen. Veckan därpå, under en taggmatch där Hogan och Orndorff mötte den massiva duon Big John Studd och King Kong Bundy, kolliderade Hogan och Orndorff av misstag och Hogan slog ner Orndorff från förklädet. När Studd och Bundy började dubbelteama Hogan hjälpte Orndorff inte till; han såg ut att ha skadat ögat i kollisionen. Det var inte förrän Studd och Bundy hade Hogan i en komprometterad position som Orndorff återvände in i ringen för att avvärja Studd och Bundy. Orndorff hjälpte sedan Hogan upp på fötter och höjde sin hand i luften och gav Hogan en clothesline följt av en piledriver.
Orndorff återförenades snart med managern Bobby Heenan och hade återigen en fejd med Hulk Hogan, bland annat en minnesvärd utomhusmatch i Toronto som drog uppskattningsvis 76 000 fans. Efter en serie av matcher utan ren utgång beslutades det att Hogan och Orndorff skulle drabbas samman i en stålbursmatch på Saturday Night’s Main Event. I burmatchen fick både Orndorff och Hogan klättra över burens topp och röra golvet samtidigt. Efter att ha granskat filmen beslutades det att det var oavgjort och matchen startades om. När matchen återupptogs tog sig Hogan lätt ut ur buren för att vinna matchen efter en leg drop, vilket avslutade deras fejd. Deras halvårslånga fejd är en av de mest anmärkningsvärda (och lönsamma) fejderna i pro wrestlingens historia.
Under Hogan-fejden skadade Orndorff allvarligt sin högra arm i en viktlyftningsolycka. Eftersom han befann sig mitt i sin stora pengaaffär med Hogan ville han inte ta ledigt för att genomgå en operation för att behandla det ordentligt, utan valde i stället att fortsätta att brottas. Efter att programmet med Hogan avslutades arbetade Orndorff på ett reducerat schema i några månader innan han tvingades ta ledigt på grund av skadan. Medan Orndorff var borta från WWF tog Bobby Heenan in en ny man ”Ravishing” Rick Rude för att ta Orndorffs plats i Heenan Family. Orndorff återvände till ringen specifikt för att avskeda Bobby Heenan och för att göra fejd med Rick Rude. Orndorff tog Oliver Humperdink som manager i sin kamp mot Rude och Heenan. Orndorffs sista ”stora” framträdande var vid den inledande Survivor Series den 26 november 1987, där han tillsammans med Hulk Hogan, Bam Bam Bigelow, Ken Patera och Don Muraco tog sig an Andre the Giant, One Man Gang, King Kong Bundy, Rick Rude och Butch Reed. Tidigt i matchen eliminerade Rude Orndorff med en roll-up.
Som ett resultat av tyngdlyftningsskadan och det faktum att Orndorff aldrig genomgick någon operation för att korrigera skadan är hans högra arm synbart mindre och mindre muskulös än hans vänstra.
Paul Orndorff drog sig tillbaka mycket tidigt 1988 på grund av sin armskada och koncentrerade sig på att driva sin bowlinghall i Fayetteville. Under den tid han var borta från sporten rapporterades han faktiskt ha dött; historien kom i flera tidningar. Avbrottet berodde på den skada på hans arm/nacke som han ådrog sig under Hogan-fejden och som han lämnade obehandlad alltför länge. Under ledigheten återhämtade sig Orndorff och började träna och återupprättade den fysik som gav honom smeknamnet ”Mr Wonderful” från början. Den enda skillnaden var att hans högra arm var märkbart mindre och försvagad på grund av en nackskada som orsakade nervskador och så småningom atrofi av hans högra biceps.
Under 1990 återvände Orndorff till den fyrkantiga cirkeln och brottade en serie matcher mot Kerry Von Erich i den oberoende kretsen. Våren 1990 skrev Orndorff på för World Championship Wrestling och debuterade som medlem i en grupp kallad ”Dudes with Attitudes” som bestod av honom själv, Sting, Lex Luger, Junkyard Dog och bröderna Steiner. Dudes stödde Sting i hans kamp mot Four Horsemen. På Clash of the Champions XI besegrade Orndorff Arn Anderson och på Great American Bash 1990 slog Orndorff ihop sig med Junkyard Dog och El Gigante för att besegra Arn Anderson, Barry Windham och Sid Vicious genom diskvalificering. Orndorff stannade kvar hos WCW till hösten 1990.
Orndorff återvände till WCW i slutet av 1992. I januari 1993 mötte han Cactus Jack, där vinnaren skulle bli manager Harley Races utvalda ersättare för en skadad Rick Rude vid Clash of the Champions. Race assisterade Orndorff i matchen och fick snabbt sällskap av Vader i sin attack mot Cactus Jack. Efter matchen förklarade Race att Paul Orndorff var hans utvalda man. Orndorff blev pinnad av Cactus Jack i en efterföljande Thunderdome-match; de två hade en intensiv fejd som inkluderade en Falls Count Anywhere-match på SuperBrawl III, som Cactus Jack vann.
När fejden med Cactus svalnade satte ”Mr Wonderful” siktet inställt på det vakanta WCW World Television Championship. Orndorff anmälde sig till en 16-manna turnering där han slog 2 Cold Scorpio, Cactus Jack, Johnny B. Badd och sedan Erik Watts i finalen för att vinna sin första WCW-titel. Orndorff, TV-mästaren, och Rick Rude, USA-mästaren, började samarbeta regelbundet, inklusive en PPV-seger över Dustin Rhodes och Kensuke Sasaki på Slamboree. Under denna tid slog Orndorff också tillbaka utmaningarna från bland annat Ron Simmons och Marcus Alexander Bagwell och höll fast vid sin tv-titel med alla nödvändiga medel. Orndorff besegrade Bagwell på ett kontroversiellt sätt genom att använda det andra repet som hävstång vid pinfallet. De två skulle senare gå vidare till en fejd om WCW World Tag Team-titeln. Orndorffs regeringstid för World TV Title innefattade även en förlust genom diskvalificering mot Johnny B Badd, efter att Maxx Payne våldsamt ingrep. Detta ledde till en kort sexmanna tag team-allians mellan Orndorff, Payne och Chris Benoit. Den 18 augusti 1993 tog Orndorffs tur slut då Ricky Steamboat vann titeln på Clash of the Champions XXIV. Efter att utan framgång ha utmanat Ricky Steamboat under hela hösten och vintern 1993 var det dags för en förändring.
När Orndorff gick i pension började han driva WCW Power Plant, där han tränade flera brottare, bland annat Natural Born Thrillers. Han hade en kort roll på skärmen under denna tid i Old Age Outlaws med Terry Funk, Arn Anderson och Larry Zbyszko för att göra fejd med den sista WCW-inkarnationen av nWo.
Den 3 februari 2005 tillkännagavs Orndorff som en av de invalda för 2005 års klass i WWE Hall of Fame. Han blev invald den 2 april på Universal Amphitheatre i Los Angeles, Kalifornien av Bobby ”The Brain” Heenan. Senare under kvällen, under Hulk Hogans inval, sågs Orndorff tydligt inte applådera när Hogan kom in på scenen.