The connections between Miami and Havana started much before the 1950s. Henry Flagler, considered to be the founder of Miami, was probably the first one to think of Miami as a Pan-American city. After building a fortune with John D. Rockefeller with Standard Oil, Flagler moved to Florida and decided to build a hotel chain along the East Coast of Florida all the way to the Caribbean. However, before he could in this new enterprise, he realized he needed a transportation system and started what would become the Florida East Coast Railway. By 1896, when Miami was incorporated, he had built FEC all the way to Biscayne Bay. In 1905, he decided to extend the railway all the way to Key West, at the time, the most populous city in the state and the closest deep water port to the planned Panama Canal. Thus, the Florida Overseas Railroad made it to Key West by 1912. 

Once in Key West, passengers could board a steamer from the Peninsular and Occidental Steamship Company (P&O) also belonging to Flagler that would take them to Havana in about six hours. As soon as the Florida Overseas Railroad started operating, the train that made it from New York to Key West was aptly called The Havana Special.

Although Flagler died in 1913, and the Florida Overseas Railroad was operational until 1935 when it was destroyed by a category 5 hurricane, the FEC continued to map itself from Jacksonville to Havana well into the 1940s.