Joint Expeditionary Base-Fort Story, commonly called simply Fort Story is a sub-installation of Joint Expeditionary Base Little Creek–Fort Story, which is operated by the United States Navy. Located in the independent city of Virginia Beach, Virginia at Cape Henry at the entrance of the Chesapeake Bay, 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 is the prime location and training environment for both U.S. Army amphibious operations and Joint Logistics-Over-the-Shore (LOTS) training events.

The base includes 1,451 acres (5.9 km²) of sandy trails, cypress swamps, maritime forest, grassy dunes and soft and hard sand beaches. The western beaches are wide, gently sloped and washed by the waters of the Chesapeake Bay. Eastern beaches are exposed to the rougher waters of the Atlantic surf.

Joint Expeditionary Base Fort Story has three historic sites. The Cape Henry Memorial Cross marks the location where the Jamestown Settlers first landed in 1607. The Old Cape Henry Light was the first lighthouse authorized and built by the Federal Government. 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.

Fort Story became a military installation in 1914 when the Virginia General Assembly gave the land to the U.S. Government "to erect fortifications and for other military purposes". The base was named for Major General John Patten Story (1841–1915), a noted coast artilleryman of his day. During World War I, Fort Story was integrated into the Coast Defenses of Chesapeake Bay, which also included Fort Monroe (the headquarters) and Fort Wool.

Fort Story remained a Coast Artillery Corps post until after World War II. The initial armament was modest. Two "emergency" batteries of rapid-fire guns were emplaced at Fort Story with weapons taken from other forts. Battery A had two 6-inch (152 mm) M1900 guns moved from Fort Monroe, and Battery B had two 5-inch (127 mm) M1900 guns moved from Fort Andrews near Boston. In 1919 the 6-inch guns were returned to Fort Monroe, while the 5-inch guns were removed from service as part of a general retirement of 5-inch guns from the Coast Artillery.

Battery Pennington, consisting of four 16-inch (406 mm) M1920 howitzers, was emplaced at Fort Story in 1922, along with a three-gun anti-aircraft battery of 3-inch (76 mm) M1917 guns. The 16-inch howitzer had a barrel length of 25 calibers; the contemporary 16-inch gun M1919 had a 50-caliber barrel. With the improved weapon location at Fort Story and a range advantage over Fort Monroe's 12-inch guns of 24,500 yards (22,400 m) versus 18,400 yards (16,800 m), the 16-inch weapons could engage attacking warships long before they could come within range of Fort Monroe. Fort Story was the only location to receive these howitzers, though a few other harbor defenses received the longer 16-inch guns in the 1920s. The artillery were not accompanied by smaller-caliber rapid-fire guns until 1942.

In 1924, the coast defense command was designated a Harbor Defense Command and entered a period of post-war inactivity which lasted until the beginning of World War II. Following regimentation of the Coast Artillery Corps, the Harbor Defenses of Chesapeake Bay were garrisoned by the 12th Coast Artillery Regiment of the regular army, with the 246th Coast Artillery Regiment as the Virginia National Guard component. In 1932 the 12th Coast Artillery was effectively redesignated as the 2nd Coast Artillery, continuing as the garrison of Chesapeake Bay. In May 1928, the first battle practice of units of the coast artillery was held since the end of World War I. A battalion of 8-inch (203 mm) railway guns fired at "hostile" ships 16,000 yards out to sea; the 1st Battalion of the 12th Coast Artillery and the 52nd Coast Artillery (Railway) participated.