The promotion was founded by Shohei "Giant" Baba and the Momota brothers, sons of Rikidozan. Baba, a former pro baseball pitcher, joined the JWA in 1960. In October, 1972, he left the JWA and formed his own group, All Japan. His group continues to promote today, with a television show on Nippon Television until 2000. Their first card was on October 21, 1972 at Machida City Gym in Tokyo, Japan.

Baba established the Pacific Wrestling Federation (PWF) as the governing body for all future titles in All Japan. In the beginning the PWF recognized a world heavyweight championship and several "regional championships" given as billing to foreign stars depending from which region they came from, but after All Japan joined the NWA, the PWF world title was downgraded to a regional championship. The PWF "President" (similar to a commissioner in a U.S. promotion, with the added task of "presenting" the belts to the winners in title bouts) from the start until 2000 was Lord James Blears and after that Stan Hansen.

As a loyal member of the NWA, All Japan enjoyed the ability to bring in foreigners, from the NWA World Heavyweight Champion on down, on frequent trips. When the NWA collapsed in the late 1980s, however, Baba distanced himself from other promoters at home and abroad, and began an exclusive system of promoting talent (both Japanese and foreign) who competed only for his promotion. With the unification of the titles in All Japan into the Triple Crown and the AJPW Unified World Tag Team Championship, as well as the promotion of talent such as Jumbo Tsuruta, Genichiro Tenryu, Mitsuharu Misawa, Toshiaki Kawada and Kenta Kobashi, the promotion was able to carve a loyal fanbase that stuck with it during the 1990s. Interpromotional matches were rare; wrestlers who arrived from other promotions, such as Hiroshi Hase, Shigeo Okumura and Yoshihiro Takayama were not given pushes.

Baba died in January 1999, leaving the promotion in the hands of top star Misawa. Misawa, disheartened with Motoko Baba's proposed direction for the company, left the group on May 28, 2000 to form a new group, Pro Wrestling NOAH. Misawa took many top wrestlers from the All Japan group. Motoko Baba inherited control of the company as a result, and she responded by bringing Genichiro Tenryu back into the company, 10 years after he and others quit under similar circumstances to Misawa to form SWS, although back then the roster had not been as decimated as it was in 2000. In addition, Stan Hansen, one of All Japan's top draws and their greatest gaijin wrestler of all-time, was forced to retire due to lumbago, taking another top-tier talent away. His last match was a tournament semifinal match for the vacant Triple Crown against Tenryu. Mrs. Baba appointed him Commissioner of All Japan's Pacific Wrestling Federation title governing body.

In 2002, at the end of a year long cross promotional angle with New Japan Pro Wrestling, three of New Japan's top stars, Keiji Mutoh, Satoshi Kojima and Kendo Kashin (Kashin has since returned to New Japan), defected to All Japan. Mutoh was rewarded by Mrs. Baba with the job of company President, and eventually all the Baba family stock was transferred to Mutoh.