Prior to World War II, Shaheen worked in publicity in Chicago.^[2] During World War II Shaheen was at the Office of Strategic Services, and was awarded the Silver Star and Legion of Merit.^[3] At OSS he was "chief of OSS Special Projects" and head of the Reports Declassification Section,^[2] and an advisor on the 1946 film O.S.S.. His friendship with William Casey, CIA Director under Ronald Reagan, derived from this period.^[4] Under President Richard Nixon, Shaheen was also "a special ambassador to Colombia".^[3]

Shaheen founded a life insurance business, selling life insurance from airport vending machines, before moving into the oil business.^[3][5] His oil industry activity included the Come By Chance Refinery in Newfoundland, Canada, which went bankrupt in 1976 owing around $500M, and was "one of the single largest bankruptcies in Canadian history to that date".^[6] In 1973 it was rumoured that Shaheen was going to found a newspaper,^[7] to be called the "New York Press".^[8] At the time his company, Shaheen Natural Resources, owned three radio stations and part of a television station, but had no experience in print media.^[8] It was reported in 1973 that he had made over $200M since World War II.^[9]

One of Shaheen's most memorable moments took place in the fall of 1974, when he chartered Queen Elizabeth 2 to bring dignitaries to a barren plot of land on the Nova Scotia mainland, opposite Bear Head, Cape Breton. The inhabitants of the land had been cleared to make way for a large oil refinery, modeled on the Come By Chance refinery in Newfoundland, that Shaheen was promoting. The refinery was never built.^[10]

Shaheen was one of the principal contributors to Richard Nixon's campaign in 1968, and in the top 100 Republican donors in 1972, giving $100,000.^[8]

In 1981, Shaheen founded the Hong Kong Deposit and Guaranty Bank.^{[citation needed]}