For as long as Henry Flagler could remember, there had been talk of one day building a canal across the Isthmus of Panama. Believing that one day the canal would be built, he worked through the Florida legislature as early as 1891 to keep his options open for building a railroad to Key West. Key West, the United States' closest deep-water port to the Canal, would not only take advantage of Cuban and Latin American trade, but would also allow significant trade possibilities with California. The opportunity finally came in 1905, when the United States announced its intention to build the Panama Canal.

Building the Over-Sea Railroad was, and remains, the most ambitious engineering feat ever undertaken by a private citizen. Seemingly insurmountable obstacles confronted the construction of the Key West Extension of the Florida East Coast Railway. The construction required many engineering innovations as well as vast amounts of labor and monetary resources.

"I regard [the Over-Sea Railroad] as second only to the Panama Canal in its political and commercial importance to the United States." - Elihu Root, Secretary of State.
At one time during construction, four thousand men were employed on the 156 mile stretch of railroad. For nearly half the distance the railroad had to be raised over water or marshland on steel and concrete bridges.

During the seven-year construction, five hurricanes threatened to halt the project, three of them resulted in significant damage and loss of life. Despite the hardships, the final link of the Over-Sea Railroad was completed in 1912 and the first official train to reach Key West pulled Henry Flagler's private Railcar No. 91.

On January 22, 1912, Henry Flagler was greeted by thousands of well-wishers. The citizens of Key West presented Flagler with mounted silver medallions made by Tiffany & Co. to commemorate the occasion and the employees presented him with an 18kt gold telegram of congratulations housed in an amazing highly decorated vermeil box also made by Tiffany & Co. The gold telegram read, "January 22, 1912. Mr. Henry M. Flagler, Key West, Fla. Congratulating you on the completion of the crowning work of your life, we trust you may long enjoy the pleasures of achievement and lead us in our loyal service to you. Employees Florida East Coast Railway."

Virtually every important artifact and document associated with the Over-Sea Railroad is now a part of the Henry Morrison Flagler Museum's extensive collections, including Railcar No. 91 itself.