The Admirals Club was conceived by AA president C.R. Smith as a marketing gimmick shortly after he was made an honorary Texas Ranger. Inspired by the Kentucky colonels and other honorary organizations, Smith decided to make particularly valued passengers "admirals" of the "Flagship fleet" (AA called its aircraft "Flagships" at the time). The list of Admirals included many celebrities, politicians and other VIPs, as well as more "ordinary" customers who had been particularly loyal to the airline.

There was no physical Admirals Club until shortly after the opening of LaGuardia Airport. During the airport's construction, New York Mayor Fiorello LaGuardia had an upper-level lounge set aside for press conferences and business meetings. At one such press conference, he noted that the entire terminal was being offered for lease to airline tenants; after a reporter asked whether the lounge would be leased as well, LaGuardia replied that it would, and a vice president of AA immediately offered to lease the premises. The airline then procured a liquor license and began operating the lounge as the "Admirals Club" in 1939.