(FORTUNE Magazine) – We can't prove it, but we suspect that the fact that every Philip Morris CEO going back to 1957 is alive and well (there are only six of them) must set some sort of record, if only for irony. Just as Philip Morris, now called Altria, is known for its, ahem, rather loyal customers, its CEOs also have a hard time kicking the habit: Average tenure is more than three times the national norm.

The cadre of Philip Morris CEOs, predictably, includes a few legendary characters: Joseph Cullman III (CEO from 1957 to 1978) was known to judge company loyalty by walking the office and noting who had an ashtray and who did not, according to the book Ashes to Ashes. Cullman was succeeded by George Weissman (1978-84), Hamish Maxwell (1984-91), and Michael Miles (1991-94).

In 1995, when New York City banned smoking in most indoor public spaces, new CEO Geoffrey Bible convinced legislators to exempt the Philip Morris headquarters at 120 Park Avenue (the city capitulated rather than risk seeing Philip Morris move out of town). But in 2003, New York City finally banned smoking in bars and revoked the company's exemption; coincidentally, CEO Louis Camillieri relocated tobacco headquarters to Richmond the same year.

While it's remarkable that a tobacco company has leaders of such longevity, it remains a mystery whether there is any correlation to cigarettes: An Altria spokesperson declined to comment on how much each of the six CEOs smoked. --A.L.