Graham debuted in the World Wide Wrestling Federation on October 25, 1975, in a tag-team match at the Boston Garden in which he and Spiros Arion defeated WWWF champion Bruno Sammartino and Dominic De Nucci. At this time The Grand Wizard became the Superstar's manager and the pair became wildly popular through their eccentric and vitriolic pre-match interviews, many of which were televised. This first stint with the promotion continued until June 1976 and included several spectacular and highly publicized battles with Sammartino in Madison Square Garden. The February 2 match drew a crowd of 27,000 spectators. Another major feud at this time was with Polish muscleman Ivan Putski.
April 1977 saw Superstar Billy Graham back in the WWWF after an agreement with promoter Vincent J. McMahon (Senior). Graham defeated Bruno Sammartino for the World Heavyweight Championship on April 30, 1977, in Baltimore, Maryland. The title win set a precedent, as previous heels who had won the WWWF title would almost immediately lose it, serving as a conduit (or "transitional champion") between fan favorite reigns. Graham would go on to hold the title for nine and a half months.
During his reign, he wrestled across America and even in Japan (February, 1978), facing well-known challengers such as former champion Bruno Sammartino, Jack Brisco, Dusty Rhodes, Pedro Morales, Don Muraco, Mil Mascaras, Strong Kobayashi and Riki Chōshū. One of Graham's most celebrated matches took place in 1977 in Miami, Florida at the famed Orange Bowl football stadium against Harley Race in a WWWF Championship Championship match which ended in a bloody one hour time-limit draw. He eventually "lost" the title to Bob Backlund on February 20, 1978.
The unforgettable post-championship battles with Dusty Rhodes were a virtual swan song for the "Superstar". Disillusioned by the premature loss of his belt, Graham left the WWWF in December 1978.
Graham returned to the now renamed World Wrestling Federation in September 1982. He debuted in the promotion with entirely new look: lean, with a bald head and mustache, and sporting black karate pants. This gimmick was not considered successful.
He soon challenged Backlund for the WWF Championship, but was unable to win the title. In his scripted response, he destroyed Backlund's championship belt by literally tearing it half. He left the promotion soon after.
Graham returned to the WWF one more time in 1986 as a fan favorite. After a few appearances, it was diagnosed that Graham required a hip replacement. The footage of Graham's hip replacement surgery was shown on WWF TV as a means to promote Graham's comeback. He returned in mid-1987 and feuded with Butch Reed for a few months, but the strain on his hip as well as his ankles also deteriorating proved to be too much. In Syracuse NY on October 27 (Thanksgiving Day) One Man Gang supposedly retired him from active competition permanently with a running splash on the concrete floor after Graham's win over Reed. In this incident, aired on the November 14, 1987 episode of Superstars Don Muraco came to Graham's aid, and Graham subsequently became Muraco's manager. Superstar Billy Graham's very last wrestling match, also against Butch Reed and at 44 years of age, actually took place on November 7, 1987, in St Louis, MO. The WWF announced that Graham was scheduled to wrestle in the main event in the first-ever Survivor Series, but Muraco took his place since Graham had now retired. Over the next year, in between bouts of surgery, Graham worked for the WWF as a commentator.
On March 14, 2004, Graham was inducted into the WWE Hall of Fame, the night before WrestleMania XX, by then-World Heavyweight Champion Triple H.
Several months later, Graham joined WWE on a swing of nine televised events where he was interviewed by Jonathan Coachman (on December 28) before performing a skit which ended with Coachman getting knocked out.
On February 25, 2005, Graham appeared at another live event, and was again interviewed by Coachman before knocking him out. Three days later, Graham appeared on Raw, where he encouraged Randy Orton to do something to make himself notable. On October 3 at WWE Homecoming, Graham participated in a Legends Ceremony with 24 other WWE legends.
He also appeared backstage on the January 23, 2006 episode of Raw.
In November 2015, Graham announced that he had signed a legends contract with the WWE to make infrequent non-wrestling appearances.