On October 2, 1972, Graham premiered in Verne Gagne's American Wrestling Association (AWA) based in Minneapolis, where he took on the moniker "Superstar". As he toured the north-central states and adjacent areas of Canada, Graham feuded with Gagne, The Crusher, The Bruiser, Wahoo McDaniel, Billy Robinson, Ken Patera and Ivan Koloff, the latter becoming his tag-team partner. By this time, Graham was integrating into his performances not only arm wrestling contests but also weightlifting challenges (mainly involving ex-Olympian Ken Patera) and posing routines.
Graham made his in–ring debut in the World Wide Wrestling Federation (WWWF) on October 25, 1975, in a tag-team match at the Boston Garden in which he and Spiros Arion defeated WWWF Heavyweight Champion Bruno Sammartino and Dominic DeNucci. At this time, The Grand Wizard became Graham's manager. Another major feud at this time was with Polish muscleman Ivan Putski. He left the WWWF soon thereafter.
Graham returned to the WWWF in April 1977 after an agreement with promoter Vincent J. McMahon. Graham defeated Bruno Sammartino for the WWWF Heavyweight Championship on April 30, 1977, in Baltimore, Maryland. Graham held the title for nine and a half months.
During his reign, he wrestled across America and in Japan (February 1978), facing challengers such as former champion Bruno Sammartino, Jack Brisco, Dusty Rhodes, Pedro Morales, Don Muraco, Mil Mascaras, Strong Kobayashi and Riki Choshu. On 25 January 1978 in Miami, Florida, Graham wrestled against Harley Race in a match which ended in a one-hour time-limit draw. Although a defeat by Bob Backlund, who was to embody the virtuous "all-American" wrestler, had been written into Graham's current contract with the WWWF, Graham suggested another outcome to McMahon: that Ivan Koloff should turn on him, thus starting a feud that would make Graham a fan favorite. McMahon refused because of the handshake deal to make Backlund the new fan favorite champion and he did not want to go back on his word. It was also unheard of for a counter-cultural character like Graham to be a fan favorite, because McMahon and many old promoters saw Graham as a confirmed heel and therefore a negative role model. Graham eventually "lost" the title to Backlund on February 20, 1978.
Another feud Graham had as champion was with Dusty Rhodes, which culminated in a Texas Bullrope match. His confrontations with Rhodes continued after Graham had been forced to drop the belt to Backlund, until he left the WWWF for a second time.
Graham returned to the now renamed World Wrestling Federation (WWF) in September 1982. He debuted in the promotion with entirely new look: lean, with a bald head and mustache, and sporting black karate pants. After his return, he attacked Backlund, destroying his championship belt. He challenged Backlund for the WWF Championship, but was unable to win the title. He left the promotion in April 1983.
Graham returned to the WWF one more time in June 1986, now as a fan favorite. After a few appearances, it was diagnosed in August that he required a hip replacement. The footage of Graham's hip replacement surgery was shown on WWF TV on September 27 as a means of promoting his comeback. He returned in mid-1987 and worked a heavy schedule from mid July to late October, feuding with Harley Race and Butch Reed. However, the strain on his hip as well as his ankles also deteriorating proved to be too much. In Syracuse on October 27, the 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. Graham's last wrestling match, also against Butch Reed and at 44 years of age, actually took place on November 7, 1987, in St Louis, Missouri. 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 class of 2004, 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. On the January 23, 2006 episode of Raw, he promoted his book and DVD. Graham parted ways with WWE in 2009.
Graham passed away on May 17, 2023.