In the early 1960's, Hennig entered the American Wrestling Association (AWA) under the tutelage of Verne Gagne. He eventually found some main event success and shared a brief AWA Tag Team Championship reign with Duke Hoffman, but frequently losing to rougher, more experienced wrestlers, he began questioning the scientific style instilled into him by Gagne and looked toward a different approach.
During the summer of 1963, Hennig formed a team with Harley Race and branded themselves as "Handsome" Harley Race and "Pretty Boy" Larry Hennig, a cocky villainous tag team with a penchant for breaking the rules to win matches. They quickly became top contenders, and on January 30, 1965, they defeated the tandem of Dick the Bruiser and The Crusher to capture the AWA World Tag Team Championship, becoming, at the time, the youngest tag team champions ever. Race and Hennig continued to feud with the Bruiser and Crusher and other top teams for the next several years, amassing three title reigns.
Verne Gagne, in particular, was a hated rival of the team and recruited many different partners to try to defeat Race and Hennig during their AWA run. Gagne and Crusher won the titles from them six months after Race and Hennig's first reign but lost them back on August 7, 1965. The team retained the titles until May 1966 when they lost to Bruiser and Crusher. They received another title shot on January 6, 1967 and defeated Bruiser and Crusher in Chicago, Illinois. This would prove to be their final reign at AWA Tag Team Champions.
On November 1, 1967, during a tag team match in Winnipeg, Hennig was in the middle of lifting Johnny Powers as another opponent rammed into him from the front. As he dropped Powers to the mat, Hennig found that his knee had bent inward. The injury ended their last title run. The AWA allowed Harley Race to select another partner to defend the championship.
Hennig made a face turn on August 10, 1974 at a television taping in Minneapolis, now sporting a full red beard and calling himself "the Axe" when he saved the High Flyers (Jim Brunzell and Greg Gagne) from an attack. The event had Hennig opposing his former allies, Nick Bockwinkel and Ray Stevens, and manager Bobby Heenan (who Bockwinkel and Stevens hired following their recent loss of the AWA World Tag Team Titles to The Crusher and Billy Robinson the previous month) as they assaulted the Flyers during an episode of AWA All-Star Wrestling.
When Harley Race returned to the AWA in 1984, he wrestled Hennig's son, Curt - a match that was fueled by Larry Hennig confronting his former tag team partner at the end of the match. The following year, Curt's first major push would be alongside his father in a feud with The Road Warriors.
Hennig also unsuccessfully challenged Bruno Sammartino for his WWF World Heavyweight Championship title.
In February 2014, Hennig made a one-off appearance in WWE at their Elimination Chamber pay-per-view, accompanying his grandson Curtis Axel and his tag team partner Ryback to the ring on the pre-show.
Hennig passed away on December 6, 2018.