They lived on Mullet Key and other barrier islands in the area, eating fish, clams, conch, oysters and whelks from the Gulf of Mexico.

[2] In 1529, the Spanish explorer Pánfilo de Narváez investigated the barrier islands after his expedition landed between St. Pete Beach and Clearwater, Florida.

Ten years later, Hernando De Soto came ashore somewhere near the southern part of Tampa Bay, beginning what would culminate in the conquest of Florida for the Spanish Empire.

[2] In 1849, a detachment of US Army engineers, including future Confederate General Robert E. Lee surveyed the area.

Egmont Key Light was not lit during the war due to the Confederate removal of essential equipment, but the lighthouse served as an observation tower for the blockade.

The United States Navy established a refugee camp on Egmont Key for Union sympathizers from west central Florida.

[4][5] Following the Civil War, the Board of Engineers for Fortifications recommended that the military reservation of Mullet Key be continued.

The island was surveyed in 1876, and the military reservations of Egmont and Mullet keys were made permanent by executive proclamation in 1882.

In 1885, interests in St. Petersburg proposed that the Orange Belt Railway be extended to a terminal on Mullet Key serving ocean-going passenger ships.

A request to sell Mullet Key, or to grant the railroad a right-of-way, was rejected by Secretary of War William Endicott because of the military reservation.

The post's features included a large barracks, a hospital, a guardhouse, a blacksmith and carpenter shop, an administration building, and mess hall with kitchen, a bakery, and a storehouse.

The site also had brick roads, concrete sidewalks, and a narrow-gauge railroad to aid in moving materials and supplies around the post.

The St. Petersburg Times reported the commission's action in its January 25, 1939, edition: Lease of Mullet Key buildings to Percy Roberts was ratified Monday by county commissioners who made no change in the tentative lease approved last week.Roberts will pay the county $50 a month for the first year and $100 a month for the next two years for the lease of two buildings on the extreme south end of the county's property on the key.The lessee will operate a daily boat service to the island and will serve fish dinners and rent fishing tackle.

Roberts envisioned creating a venue on the island appealing to clubs, associations, and other organizations for group outings of members for fishing, sightseeing, and "dining on fried mullet".

Hobo operated daily from the Bee Line Ferry Terminal at St. Petersburg's Pinellas Point, pulling away from the dock early morning and leaving for the return trip late afternoon.

The facility at best was austere, but one who was tired and hungry could get a good night's sleep; plenty of coffee, a hearty serving of bacon and eggs for breakfast; any of an assortment of sandwiches for lunch; and, a family style meal of fried mullet with all the trimmings for supper.

Rubert "Rube" Allyn, a writer for the St. Petersburg Times, included in his March 28, 1939, column, "Along the Waterfront": When the Pinellas county commissioners leased the old Fort De Soto, and Mullet Key to Percy Roberts, they did a fine thing for the tourists by opening up the vast uninhabited reaches of Mullet Key and the old fort to exploration parties ... Today for a nominal fee, one can take a boat at Pinellas Point, and go to Mullet Key, land at the old Quarantine dock, enjoy an old-fashioned fish dinner prepared in the same manner as the pioneers of 50 years ago, by the Roberts family, and explore miles of uninhabited beaches, bayous, and the old Spanish–American War fort ...[10]In less than two years, Mullet Key Lodge became well established and profitable.

That pending transaction was reported by the St. Petersburg Times on December 18, 1940: Mullet Key purchased by the county from the Treasury department in 1938 for $12,500 will soon be taken over by the United States Army Air Corps for use as a bombing range.

The Quartermaster Storehouse Museum is a recreation of the original quartermaster storehouse building built between 1900 and 1906, and was duplicated in 1999 using historical photographs, Army engineering condition reports, government documents, and was funded by the Friends of Fort De Soto Inc. and the Pinellas County Parks and Conservation Resources Department.

Park staff built the 833-square-foot wooden structure, which contains updated features not found in the original building, including air conditioning, fiber-optic lighting, concealed insulation, and a fire suppression system.

In the 1990s, the Pinellas County Parks Department provided a historical interpretation of the military post site, which originally contained 29 buildings, including a hospital, stable, 100-foot-long barrack, guard house, a shop for blacksmiths and carpenters, an administration office, a mess hall, a bake house, and a storehouse, which then gave inspiration to the park staff and volunteers to propose the construction of one of these post buildings.

Upon entering the museum, visitors are greeted by a mannequin quartermaster in a glass case surrounded by supplies that he would have issued to the soldiers.

There are also various display cases that contain recovered artifacts from the park and World War II history, including an original practice bomb, weapons, military badges, and ammunition, as well as other early 20th century items, such as a woman’s dress, a deck of playing cards, and a rattlesnake skin.

One arm faces the Gulf of Mexico, running from the Tampa Bay entrance channel north to Bunces Pass.

[15] Because waves and currents, and the occasional storm, are constantly reworking the sand that makes up a barrier island, the shape and area of Mullet Key varies over time.

However, due to factors such as habitat loss and increased abundance of the brown-headed cowbird (a brood parasite), species such as the mangrove cuckoo, black-whiskered vireo, and prairie warbler no longer breed in this location.

The Florida Fish and Wildlife Conservation Commission (FWC) began removing Australian pines from North Beach in the park in 2015.