Orndorff podpisał kontrakt z World Wrestling Federation pod koniec 1983 roku i zadebiutował w styczniu 1984 roku z „Rowdy” Roddy Piperem jako menadżerem. Piper nazwał Paula Orndorffa „Mr. Wonderful,” przydomek, którego używał do tej pory. Orndorff zadebiutował w WWF przeciwko Salvatore Bellomo w nocy, kiedy Hulk Hogan pokonał The Iron Sheik o WWF World Heavyweight Title i „narodziła się Hulkamania”, 23 stycznia 1984 roku w Madison Square Garden. Orndorff stał się jednym z pierwszych ludzi, którzy wyzwali do walki o tytuł mistrza świata, strzelając prosto do main eventu niecały miesiąc po swoim debiucie. Hogan pozbył się pretendenta i ruszył dalej, podczas gdy Orndorff walczył z różnymi przeciwnikami, w tym z Intercontinental Championem Tito Santaną. Kiedy Piper zaatakował Jimmy’ego Snukę na planie Piper’s Pit, Orndorff (jak również Bob Orton, Jr.) pomagał Rowdy One w jego walkach. Orndorff i Piper często stawiali czoła Snuce i „The Tonga Kid” w rywalizacji tag team.
Na koniec 1984 roku, atak Roddy’ego Pipera na Cyndi Lauper (kayfabe) przyniósł Orndorffa i Pipera na kursie kolizyjnym z Hulkiem Hoganem i Mr. T. Waśń Hogana z Piperem oznaczała również, że Orndorff został wrzucony z powrotem do głównego wydarzenia; pokonał Tony’ego Atlasa na The War to Settle the Score, a następnie odegrał rolę w głównym wydarzeniu. Wypadek po The War to Settle the Score doprowadził do powstania WrestleManii, gdzie Hogan i Mr. T (wspierani przez Jimmy’ego Snukę) zmierzyli się z „Rowdy” Roddy Piperem i Paulem Orndorffem w głównym wydarzeniu. Ingerencja Ortona pod koniec meczu nie powiodła się, gdy przypadkowo uderzył Orndorffa gipsem na ramieniu, pozwalając Hoganowi przypiąć Orndorffa i wygrać mecz dla swojej drużyny. Obwiniając Orndorffa za przegraną, Piper i Orton zaatakowali go w pierwszym odcinku Saturday Night’s Main Event. Później wieczorem, Orndorff wbiegł do ringu, aby wyrównać szanse, gdy Piper i Orton przygotowywali się do podwójnego zespołu Hulka Hogana. Umocnił swój status babyface, publicznie zwalniając menedżera Bobby’ego Heenana krótko po tym.
Orndorff i Hogan zaczęli łączyć się w pary, aby feudować z Piperem i Ortonem, mierząc się z nimi w zawodach tag teamów w całym kraju. Waśń Orndorffa z Piperem i Ortonem trwała nadal, podczas gdy Hogan zaczął bronić swojego tytułu przed innymi pretendentami; Orndorff zmierzył się zarówno z Ortonem, jak i Piperem w indywidualnych zawodach, zazwyczaj bez rozstrzygającego rezultatu. Po zwolnieniu Bobby’ego Heenana jako jego menadżera, Mózg umieścił 25 000 dolarów nagrody za Orndorffa, płatne dla każdego, kto mógłby go zranić. Kiedy nikomu się to nie udało, Heenan podniósł nagrodę do 50.000 dolarów. Jednym z pierwszych ludzi, którzy próbowali odebrać nowy, wyższy bonus był sam Roddy Piper, ale ich mecze tak bardzo wymknęły się spod kontroli, że Bruno Sammartino został wyznaczony na specjalnego sędziego w nadziei na utrzymanie pokoju. Zamiast utrzymania pokoju, Sammartino stał się celem dla Ortona i Pipera, co doprowadziło do połączenia sił Orndorffa i Sammartino. Orndorff współpracował z różnymi przeciwnikami w walkach z Piperem i Ortonem, w tym z André the Giant. W lutym 1986 roku, Bobby Heenan wykorzystał mecz pomiędzy Hulkiem Hoganem i Donem Muraco jako okazję, aby King Kong Bundy zaatakował Hogana, ustawiając ich mecz na WrestleManii 2. Podczas gdy Hogan walczył z Bundy’m, Orndorff walczył z Donem Muraco w meczu, który zakończył się podwójnym count out.
Frustracje Orndorffa były jeszcze bardziej podsycane przez Adriana Adonisa, który brał każdą okazję, że mógł szydzić z Orndorffa (w tym odnosząc się do niego jako „Hulk Jr.”), mówiąc, że zmiękł od teamingu z Hoganem. Adonis wciąż irytował Orndorffa, posuwając się do tego, że ośmielił Paula Orndorffa do udowodnienia jak bliskie były jego relacje z Hulkiem Hoganem. Podczas transmitowanej w telewizji rozmowy telefonicznej z Hulkiem Hoganem, Orndorffowi powiedziano, że Hogan jest zbyt zajęty treningiem, aby podejść do telefonu, co bardzo zdenerwowało Orndorffa. Następnym razem, gdy Hogan i Orndorff połączyli siły, przeciwko Moondogs, Orndorff przez większość meczu walczył sam, próbując zdystansować Hogana, zdobywając zwycięski pin. W następnym tygodniu, podczas tag matchu, gdzie Hogan i Orndorff zmierzyli się z masywnym duetem Big John Studd i King Kong Bundy, Hogan i Orndorff przypadkowo zderzyli się i Hogan zrzucił Orndorffa z apronu. Kiedy Studd i Bundy zaczęli podwajać Hogana, Orndorff nie pomógł; wyglądał jakby uszkodził oko podczas zderzenia. Dopiero gdy Studd i Bundy mieli Hogana w kompromitującej pozycji, Orndorff ponownie wszedł do ringu, aby odeprzeć Studda i Bundy’ego. Orndorff następnie pomógł Hogan do jego stóp i podniósł rękę w powietrze i dał Hogan clothesline następnie piledriver.
Orndorff wkrótce ponownie zjednoczył się z menedżerem Bobby Heenan i po raz kolejny feuded z Hulk Hogan, w tym pamiętny mecz na świeżym powietrzu w Toronto, który przyciągnął około 76.000 fanów. Po serii meczów bez czystego wyniku zdecydowano, że Hogan i Orndorff zmierzą się w pojedynku w stalowej klatce na Saturday Night’s Main Event. W pojedynku w klatce zarówno Orndorff jak i Hogan wspięli się na szczyt klatki i dotknęli podłogi w tym samym czasie. Po przejrzeniu materiału filmowego zdecydowano, że jest remis i mecz został wznowiony. Po wznowieniu meczu, Hogan z łatwością wyszedł z klatki i wygrał mecz po leg drop, kończąc tym samym ich waśń. Ich półroczny feud jest jednym z najbardziej godnych uwagi (i dochodowych) feudów w historii pro wrestlingu.
Podczas feud Hogana, Orndorff poważnie zranił swoje prawe ramię w wypadku przy podnoszeniu ciężarów. Ponieważ był w środku jego wielkiego biegu pieniędzy z Hogan, nie chciał wziąć wolnego czasu, aby mieć operację, aby prawidłowo leczyć, decydując się zamiast tego, aby kontynuować wrestling. Po zakończeniu programu z Hoganem, Orndorff przez kilka miesięcy pracował w zmniejszonym wymiarze godzin, zanim został zmuszony do wzięcia wolnego z powodu kontuzji. Podczas gdy Orndorff był z dala od WWF, Bobby Heenan sprowadził nowego człowieka „Ravishing” Rick Rude, który zajął miejsce Orndorffa w Heenan Family. Orndorff powrócił do ringu specjalnie po to, aby zwolnić Bobby’ego Heenana i stoczyć feud z Rickiem Rude. Orndorff wziął Olivera Humperdinka jako swojego menadżera w walce z Rude’m i Heenanem. Ostatni „duży” występ Orndorffa miał miejsce na inauguracyjnym Survivor Series 26 listopada 1987 roku, gdzie wraz z Hulkiem Hoganem, Bam Bam Bigelowem, Kenem Paterą i Donem Muraco zmierzył się z Andre the Giant, The One Man Gang, King Kong Bundy, Rick Rude i Butch Reed. Wcześnie w meczu, Rude wyeliminował Orndorff z roll-up.
W wyniku kontuzji podnoszenia ciężarów i fakt, że Orndorff nigdy nie miał operacji, aby poprawić uraz, jego prawe ramię jest widocznie mniejsze i mniej muskularne niż jego lewa.
Paul Orndorff przeszedł na emeryturę w bardzo wczesnym 1988 roku z powodu kontuzji ramienia i skupił się na prowadzeniu swojej kręgielni w Fayetteville. Podczas jego czasu z dala od sportu był rzeczywiście zgłoszone, że zmarł, historia się kilka gazet. Czas wolny był spowodowany kontuzją ramienia/szyi, której doznał podczas walki z Hoganem i której nie leczył zbyt długo. Orndorff wyzdrowiał i zaczął ćwiczyć, odbudowując sylwetkę, dzięki której zyskał przydomek „Mr. Wonderful”. Jedyną różnicą było to, że jego prawe ramię było zauważalnie mniejsze i osłabione z powodu urazu szyi, który spowodował uszkodzenie nerwów i ostatecznie zanik jego prawego bicepsa.
W 1990 roku Orndorff powrócił do squared circle, wrestling serię meczów z Kerry Von Erich na niezależnym obwodzie. Wiosną 1990 roku Orndorff podpisał kontrakt z World Championship Wrestling, debiutując jako członek grupy zwanej „Dudes with Attitudes”, w skład której wchodził on sam, Sting, Lex Luger, Junkyard Dog i The Steiner Brothers. The Dudes wspierali Stinga w jego walce z Four Horsemen. Na Clash of the Champions XI Orndorff pokonał Arna Andersona, a na 1990 Great American Bash, Orndorff połączył siły z Junkyard Dogiem i El Gigante i pokonał Arna Andersona, Barry’ego Windhama i Sida Viciousa przez dyskwalifikację. Orndorff pozostał z WCW do jesieni 1990 roku.
Orndorff wrócił do WCW pod koniec 1992 roku. W styczniu 1993 roku zmierzył się z Cactusem Jackiem, a zwycięzca był wybranym przez menedżera Harleya Race’a zastępcą kontuzjowanego Ricka Rude’a na Clash of the Champions. Race asystował Orndorffowi w pojedynku i szybko dołączył do niego Vader w ataku na Cactusa Jacka. Po meczu Race oświadczył, że Paul Orndorff jest jego wybrańcem. Orndorff został przypięty przez Cactusa Jacka w późniejszym meczu Thunderdome; ci dwaj mieli intensywny feud, w tym Falls Count Anywhere match na SuperBrawl III, który Cactus Jack wygrał.
Po tym jak feud z Cactusem ostygł, „Mr. Wonderful” ustawił swoje cele na wakujące WCW World Television Championship. Orndorff zapisał się do 16 osobowego turnieju pokonując 2 Cold Scorpio, Cactus Jack, Johnny B. Badd, a następnie Erik Watts w finale, aby wygrać swój pierwszy tytuł WCW. Orndorff, mistrz TV, i Rick Rude, mistrz USA, zaczęli regularnie współpracować, włączając w to zwycięstwo PPV nad Dustinem Rhodesem i Kensuke Sasakim na Slamboree. W tym czasie Orndorff odpierał także ataki między innymi Rona Simmonsa i Marcusa Alexandra Bagwella, utrzymując się przy swoim tytule Television za wszelką cenę. Orndorff pokonał Bagwella kontrowersyjnie, używając drugiej liny jako dźwigni podczas pinfallu. Ta dwójka miała później walczyć o WCW World Tag Team Title. Orndorffa World TV Title panowanie również zawierał dyskwalifikacji straty do Johnny B Badd, po Maxx Payne brutalnie interweniował. To doprowadziło do krótkiego, sześcioosobowego sojuszu tag teamowego pomiędzy Orndorffem, Payne’m i Chrisem Benoitem. 18 sierpnia 1993 roku, szczęście Orndorffa skończyło się, gdy Ricky Steamboat zdobył tytuł na Clash of the Champions XXIV. Po bezskutecznym wyzwaniu Ricky Steamboat przez całą jesień i zimę 1993 roku, nadszedł czas na zmianę tempa.
Po przejściu Orndorffa na emeryturę zaczął prowadzić WCW Power Plant, gdzie trenował kilku wrestlerów, w tym Natural Born Thrillers. Miał krótką rolę na ekranie w tym czasie w Old Age Outlaws z Terry Funk, Arn Anderson, i Larry Zbyszko do feud z ostatniej inkarnacji WCW nWo.
On 3 lutego 2005 roku, Orndorff został ogłoszony jako jeden z inductees dla Class of 2005 do WWE Hall of Fame. Został on wprowadzony 2 kwietnia w Universal Amphitheatre w Los Angeles w Kalifornii przez Bobby’ego „The Brain” Heenana. Później w nocy, podczas indukcji Hulka Hogana, Orndorff był widziany wyraźnie nie klaszcząc, gdy Hogan wszedł na scenę.