Orndorff signe avec la World Wrestling Federation fin 1983 et fait ses débuts en janvier 1984 avec « Rowdy » Roddy Piper comme manager. Piper a surnommé Paul Orndorff « Mr. Wonderful », un surnom qu’il a toujours utilisé depuis. Orndorff a fait ses débuts à la WWF contre Salvatore Bellomo le soir où Hulk Hogan a battu The Iron Sheik pour le titre de champion du monde poids lourd de la WWF et que la « Hulkamania était née », le 23 janvier 1984 au Madison Square Garden. Orndorff est devenu l’une des premières personnes à défier le titre mondial, se hissant directement au rang d’événement principal moins d’un mois après ses débuts. Hogan élimine le challenger et passe à autre chose tandis qu’Orndorff combat divers adversaires dont le champion intercontinental Tito Santana. Lorsque Piper agresse Jimmy Snuka sur le plateau de Piper’s Pit, Orndorff (ainsi que Bob Orton, Jr.) aide le Rowdy One dans ses combats. Orndorff et Piper affrontent souvent Snuka et « The Tonga Kid » dans des compétitions en tag team.
Vers la fin de l’année 1984, l’agression de Roddy Piper sur Cyndi Lauper (kayfabe) amène Orndorff et Piper sur une trajectoire de collision avec Hulk Hogan et Mr. T. La querelle entre Hogan et Piper a également permis à Orndorff de revenir sur le devant de la scène ; il a battu Tony Atlas à The War to Settle the Score et a ensuite joué un rôle dans le main event. Les retombées de The War to Settle the Score conduisent à la création de WrestleMania, avec Hogan et Mr. T (soutenu par Jimmy Snuka) affrontant « Rowdy » Roddy Piper et Paul Orndorff dans le main event. L’interférence d’Orton à la fin du match se retourne contre lui lorsqu’il frappe accidentellement Orndorff avec le plâtre sur son bras, permettant à Hogan de pincer Orndorff et de gagner le match pour son équipe. Blâmant Orndorff pour cette défaite, Piper et Orton l’attaquèrent lors du premier épisode de Saturday Night’s Main Event. Plus tard dans la soirée, Orndorff se précipite sur le ring pour égaliser les chances lorsque Piper et Orton se préparent à faire une double équipe avec Hulk Hogan. Il a solidifié son statut de babyface en virant publiquement le manager Bobby Heenan peu après.
Orndorff et Hogan ont commencé à faire équipe pour se battre avec Piper et Orton, les affrontant dans des compétitions en tag team dans tout le pays. La querelle d’Orndorff avec Piper et Orton continue de faire rage tandis que Hogan commence à défendre son titre contre d’autres prétendants ; Orndorff affronte à la fois Orton et Piper en compétition individuelle, généralement sans issue concluante. Après avoir viré Bobby Heenan comme manager, le Cerveau mit une prime de 25 000 dollars sur Orndorff, payable à quiconque pourrait le blesser. Comme personne n’y parvient, Heenan augmente la prime à 50 000 dollars. L’un des premiers hommes à essayer de réclamer la nouvelle prime, plus élevée, fut Roddy Piper lui-même, mais leurs matchs devinrent tellement incontrôlables que Bruno Sammartino fut nommé arbitre spécial dans l’espoir de maintenir la paix. Au lieu de maintenir la paix, Sammartino est devenu une cible pour Orton et Piper, ce qui a conduit Orndorff et Sammartino à faire équipe. Orndorff a fait équipe avec une variété d’adversaires dans ses combats avec Piper et Orton, y compris André the Giant. En février 1986, Bobby Heenan profite d’un match entre Hulk Hogan et Don Muraco pour que King Kong Bundy attaque Hogan, préparant ainsi leur match de WrestleMania 2. Pendant que Hogan combattait Bundy, Orndorff affrontait Don Muraco dans un match qui se termina par un double décompte.
Les frustrations d’Orndorff étaient encore plus alimentées par Adrian Adonis, qui profitait de toutes les occasions possibles pour se moquer d’Orndorff (notamment en l’appelant » Hulk Jr « ), en disant qu’il était devenu mou à force de faire équipe avec Hogan. Adonis continuait à irriter Orndorff, allant jusqu’à mettre Paul Orndorff au défi de prouver à quel point sa relation avec Hulk Hogan était vraiment étroite. Lors d’un appel téléphonique télévisé à Hulk Hogan, Orndorff se voit répondre que Hogan est trop occupé à s’entraîner pour venir au téléphone, ce qui exaspère Orndorff au plus haut point. La fois suivante où Hogan et Orndorff ont fait équipe, contre les Moondogs, Orndorff a lutté la plupart du match tout seul dans une tentative de mettre en scène Hogan, marquant le pin gagnant. La semaine suivante, lors d’un tag match où Hogan et Orndorff affrontaient le duo massif de Big John Studd et King Kong Bundy, Hogan et Orndorff se heurtaient accidentellement et Hogan faisait tomber Orndorff du tablier. Lorsque Studd et Bundy commencent à faire une double équipe avec Hogan, Orndorff n’aide pas ; il semble s’être blessé à l’œil dans la collision. Ce n’est que lorsque Studd et Bundy avaient mis Hogan dans une position compromise qu’Orndorff remontait sur le ring pour repousser Studd et Bundy. Orndorff aida ensuite Hogan à se relever et leva sa main en l’air et donna à Hogan une corde à linge suivie d’un piledriver.
Orndorff retrouva bientôt son manager Bobby Heenan et se battit à nouveau contre Hulk Hogan, notamment lors d’un mémorable match en plein air à Toronto qui attira environ 76 000 fans. Après une série de matchs sans issue claire, il fut décidé que Hogan et Orndorff s’affronteraient dans un match en cage d’acier lors de l’émission Saturday Night’s Main Event. Dans ce match en cage, Orndorff et Hogan passent par le haut de la cage et touchent le sol en même temps. Après avoir revu les images, il était décidé qu’il y avait match nul et le match était repris. Une fois le match repris, Hogan sort facilement de la cage pour gagner le match après un leg drop, mettant fin à leur querelle. Leur querelle d’une demi-année est l’une des querelles les plus notables (et les plus rentables) de l’histoire de la lutte professionnelle.
Pendant la querelle Hogan, Orndorff se blesse gravement au bras droit dans un accident d’haltérophilie. Parce qu’il était au milieu de son programme de gros sous avec Hogan, il ne voulait pas prendre le temps de se faire opérer pour le soigner correctement, choisissant plutôt de continuer à catcher. Après la fin du programme avec Hogan, Orndorff a travaillé à un horaire réduit pendant quelques mois avant d’être obligé de prendre un congé à cause de sa blessure. Pendant qu’Orndorff était absent de la WWF, Bobby Heenan fit entrer un nouvel homme « Ravishing » Rick Rude pour prendre la place d’Orndorff dans la famille Heenan. Orndorff remonte sur le ring dans le but précis de virer Bobby Heenan et de se battre avec Rick Rude. Orndorff prit Oliver Humperdink comme manager dans sa lutte avec Rude et Heenan. La dernière » grande » apparition d’Orndorff fut lors de la première édition des Survivor Series le 26 novembre 1987, où il fit équipe avec Hulk Hogan, Bam Bam Bigelow, Ken Patera et Don Muraco pour affronter Andre the Giant, the One Man Gang, King Kong Bundy, Rick Rude et Butch Reed. Au début du match, Rude élimine Orndorff avec un roll-up.
En raison de la blessure en haltérophilie et du fait qu’Orndorff n’a jamais été opéré pour corriger la blessure, son bras droit est visiblement plus petit et moins musclé que le gauche.
Paul Orndorff prend sa retraite au tout début de 1988 en raison de sa blessure au bras et se concentre sur la gestion de son bowling à Fayetteville. Pendant son temps loin du sport, on a effectivement rapporté qu’il était mort ; l’histoire a fait plusieurs journaux. Le temps d’arrêt est dû à la blessure au bras et au cou qu’il a subie pendant la querelle avec Hogan et qui n’a pas été traitée pendant trop longtemps. Grâce à ce congé, Orndorff se rétablit et commença à s’entraîner, retrouvant le physique qui lui avait valu le surnom de « Mr Wonderful ». La seule différence était que son bras droit était sensiblement plus petit et affaibli en raison d’une blessure au cou qui a provoqué des lésions nerveuses et finalement l’atrophie de son biceps droit.
En 1990, Orndorff est revenu dans le cercle carré, luttant une série de matchs contre Kerry Von Erich sur le circuit indépendant. Au printemps 1990, Orndorff signe avec la World Championship Wrestling, faisant ses débuts en tant que membre d’un groupe appelé les « Dudes with Attitudes » composé de lui-même, Sting, Lex Luger, Junkyard Dog, et les frères Steiner. Les Dudes ont soutenu Sting dans son combat contre les Four Horsemen. A Clash of the Champions XI, Orndorff bat Arn Anderson et au Great American Bash 1990, Orndorff fait équipe avec le Junkyard Dog et El Gigante pour battre Arn Anderson, Barry Windham, et Sid Vicious par disqualification. Orndorff reste à la WCW jusqu’à l’automne 1990.
Orndorff revient à la WCW à la fin de 1992. En janvier 1993, il affronte Cactus Jack, le vainqueur étant le remplaçant choisi par le manager Harley Race pour remplacer un Rick Rude blessé au Clash of the Champions. Race assistait Orndorff dans le match et était rapidement rejoint par Vader dans son attaque contre Cactus Jack. Après le match, Race déclarait que Paul Orndorff était son homme choisi. Orndorff fut épinglé par Cactus Jack lors d’un match ultérieur au Thunderdome ; les deux hommes eurent une intense querelle, y compris un match Falls Count Anywhere à SuperBrawl III, que Cactus Jack remporta.
Après que la querelle avec Cactus se soit calmée, « Mr. Wonderful » jeta son dévolu sur le championnat mondial de télévision vacant de la WCW. Orndorff s’inscrit à un tournoi de 16 hommes en battant 2 Cold Scorpio, Cactus Jack, Johnny B. Badd, puis Erik Watts en finale pour remporter son premier titre WCW. Orndorff, champion de la télévision, et Rick Rude, champion des États-Unis, commencent à faire équipe régulièrement, avec notamment une victoire en PPV contre Dustin Rhodes et Kensuke Sasaki à Slamboree. Pendant cette période, Orndorff repousse également les défis de Ron Simmons et Marcus Alexander Bagwell, s’accrochant à son titre de champion de télévision par tous les moyens. Orndorff bat Bagwell de manière controversée, en utilisant la deuxième corde pour faire levier lors de la chute. Les deux hommes s’affronteront plus tard pour le titre mondial Tag Team de la WCW. Le règne d’Orndorff pour le titre mondial de télévision comprend également une défaite par disqualification contre Johnny B Badd, après une violente intervention de Maxx Payne. Cela a conduit à une brève alliance de tag team de six hommes entre Orndorff, Payne et Chris Benoit. Le 18 août 1993, la chance d’Orndorff tourne puisque Ricky Steamboat remporte le titre à Clash of the Champions XXIV. Après avoir défié sans succès Ricky Steamboat tout au long de l’automne et de l’hiver 1993, il était temps de changer de rythme.
Après la retraite d’Orndorff, il commença à diriger la WCW Power Plant, où il entraîna plusieurs catcheurs dont les Natural Born Thrillers. Il a un bref rôle à l’écran pendant cette période dans les Old Age Outlaws avec Terry Funk, Arn Anderson et Larry Zbyszko pour feuder avec la dernière incarnation de la nWo à la WCW.
Le 3 février 2005, Orndorff a été annoncé comme l’un des intronisés de la classe 2005 du WWE Hall of Fame. Il a été intronisé le 2 avril à l’Universal Amphitheatre de Los Angeles, en Californie, par Bobby « The Brain » Heenan. Plus tard dans la nuit, pendant l’intronisation de Hulk Hogan, Orndorff a été vu clairement ne pas applaudir lorsque Hogan est arrivé sur scène.