In 1976, he challenged Bruno Sammartino for the WWWF Heavyweight Championship. This was a huge draw around the northeastern part of the United States and at Madison Square Garden, and was one of Sammartino's last great challengers before losing the title to Superstar Billy Graham, which ended his second, shorter WWF title reign. When Bob Backlund later won the title, Patera also unsuccessfully challenged him.
In 1980, he held the WWF's Intercontinental Championship.
In 1985, he returned to feud with Hulk Hogan, and also assisted Big John Studd in his feud with André the Giant, most notably helping Studd cut Andre's hair after both had attacked him.
The WWF brought Patera back to the company in the spring of 1987, airing vignettes on WWF TV. He was in top physical condition at this point, and his appearance had changed, as he wore natural brown hair, rather than his previous bleached blond look. To ensure he would be accepted as a babyface, he claimed that former manager Bobby Heenan had abandoned him and "sold him down the river" while he was in prison. Patera and Heenan held a debate to air their differences, which naturally turned into a physical confrontation between the two that culminated in Patera swinging Heenan with a belt around his neck, causing Heenan to appear on television with a neck brace for months. Patera then began feuding with the Heenan Family (at the time composed of Paul Orndorff, Harley Race, King Kong Bundy and Hercules). In his first match back at Madison Square Garden, the final match of the night, he defeated The Honky Tonk Man via submission with a bearhug, to a huge ovation. Some wrestling publications speculated that Patera would reunite with Heenan to face Hulk Hogan in the main event of WrestleMania IV. But his push was short-lived. Shortly after his return, Patera ruptured the biceps tendon in his right arm, which led him to miss some time and re-emerge afterward with a stiff and bulky full-length brace for protection. Within six months, Patera was being defeated by newer, younger talent and found himself floundering in a mid-card tag team with fellow Oregonian Billy Jack Haynes. In his final televised WWF matches in late 1988 (losses to Bad News Brown and "Outlaw" Ron Bass), commentators Gorilla Monsoon and Lord Alfred Hayes remarked on-air that Patera's skills were in decline and that he should consider retirement.