Located in the independent city of Virginia Beach, Virginia at Cape Henry at the entrance of the Chesapeake Bay,[1] it offers a unique combination of features including dunes, beaches, sand, surf, deep-water anchorage, variable tide conditions, maritime forest and open land.

The base includes 1,451 acres (5.9 km²) of sandy trails, cypress swamps, maritime forest, grassy dunes and soft and hard sand beaches.

At the Battle of the Virginia Capes Monument, there is a statue of French Admiral François Joseph Paul, comte de Grasse to commemorate the famous sea battle on September 5, 1781, which prevented the British from reaching Yorktown during the American Revolutionary War.

Also of historical interest, the new Cape Henry Lighthouse was completed in 1881 and is still maintained by the U.S. Coast Guard as an active coastal beacon.

The passenger station built in 1902 and served by the original Norfolk Southern Railway was restored late in the 20th century and is used as an educational facility by the Army.

The base was named for Major General John Patten Story (1841–1915), a noted coast artilleryman of his day.

Fort Story remained a Coast Artillery Corps post until after World War II.

[13] In 1941, prior to the United States entering World War II, more land was acquired at Fort Story.

Following the American entry into World War II two four-gun batteries of 155 mm (6.1 in) guns were deployed at Fort Story; circular concrete "Panama mounts" were built to improve their firing positions.

As a result of a 2005 Base Realignment and Closure recommendation, Fort Story operations were transferred to the United States Navy.