The recorded history of the island known as Mullet Key began in February 1849 when a group of United States Army Engineers, aboard the schooner Phoenix, anchored offshore to survey the coastline for possible use as a coastal defense area. Among them was a young Brevet Colonel named Robert E. Lee. The four engineers were studying the islands at the mouth of Tampa Bay -- Passage, Egmont, and Mullet Keys. In March 1849, the army engineers recommended Egmont and Mullet Keys for military utilization thereby prohibiting any private use or development.

The Civil War broke out in 1861, with no fortification on either Mullet or Egmont Keys. The two islands played a minor role during the Civil War. Union troops set up a blockade using the two islands. Any confederates attempting to run the blockade could be seen by troops perched atop the Egmont Key lighthouse.

The first signs of construction on the Mullet Key military post began in November 1898. During the first six months, a 275-foot wharf extending into Tampa Bay was constructed, as well as an office building, a mess hall, quarters for the workmen, and a stable. A narrow-gauge railway ran between the wharf and a construction plant, with a spur line running to the future battery site. In March 1899, the crew was ready to begin pouring the foundation of the mortar battery. The land had been cleared and the foundation forms were set. There was one small problem. The stone, which was being transported by sailing ships, had not arrived from New York and New Jersey.

In place of the stone, the workers used shell. The shell concrete formula worked so well in the foundation that it was decided, when the stone arrived on May 31, 1899, that they simply added the stone to the shell, sand, and cement mix to complete the construction of the walls and ceiling.

On April 4, 1900, the military reservation was named Fort De Soto after the Spanish explorer Hernando De Soto. Fort De Soto was officially a subpost of Fort Dade on Egmont Key at that time.

Captain Thomas H. Rees, engineer officer in charge of construction, announced the completion of the mortar battery on May 10, 1900, fourteen months after the first shovel of dirt was turned. He also could boast that the project stayed within its $155,000 budget. In fact, there was a balance of $16.73 remaining.