The land of this military post goes back 400 years to when colonists arrived in 1607 on the Chesapeake Bay, and called it Cape Henry. It had a commanding view, and firing position over the entrance to Chesapeake, and was mainly a shore battery. Three hundred years later, the Virginia General Assembly donated Cape Henry to the U.S government, and following shortly after, in 1914, a military post named Fort Story was built.

Some major changes occurred for the fort during WWI and WWII. It became part of the Coast Defenses of Chesapeake Bay, was designated as a Harbor Defense Command, and eventually became the headquarters of the Harbor Defense Command. However, after WWII, the 458th Amphibious Truck Company and the Army DUKWS arrived for the first amphibious training. As a result, in 1946, the Transportation Training Command, at Eustis, took over the installation and the post was designated a Transportation Corps installation. Six years later it became a Class I sub-installation of Fort Eustis. Presently, Fort Story is part of the U.S Army Garrison, seventh group, and houses the Eleventh Transportation Battalion Terminal.

In World War Two, this site became a training and practice center for developing the then radical concept of massive shore landings, known then and now as amphibious assaults. An early example of joint operations training, four facilities were developed on the site, Camp Bradford and Camp Shelton (named for the former landowners), and Frontier Base and Amphibious Training Base.

Prior to World War Two there was little concept of an amphibious assault; troops landed, but they either docked or were carried ashore by boat. The British had developed combined force operations as far back as the Napoleon Wars, and the Union had launched a massive landing by boat against the Confederacy during the Civil War, but nothing like what the US of World War Two had in mind. The amphibious concept involved a much more closely coordinated operation of Navy launched amphibious tracked landing vehicles, with close shore bombardment support and Marine or Army troops storming beaches. Nothing quite like this had ever been done; the Imperial Japanese landed in motorized boats; Nazi Germany had conducted an air and sea assault on Crete, but the new US concept was to use water-to-land tracked vehicles.

Thanks to practice and training at Navy bases, especially what would later be Joint Base Little Creek, the US made amphibious assault a specialty, successfully conducted at Morocco and Algeria, Sicily, Salerno, and Anzio, and the largest amphibious assault ever, the Normandy Landings. In the Pacific Theater, the Marine Corps honed amphibious assault to a fine edge, making dozens of island beach assaults.

Camp Bradford, at Little Creek, originally focused on training Seabees (Construction Battalions) and later trained LSTs (Landing Ship, Tanks) for the Normandy Landings. Camp Shelton, also at Little Creek, trained bluejackets for gunnery on merchant ships. The Frontier Base served as a training and housing center for troops destined for Europe.

The Amphibious Training Base was where the real development was happening; all kinds of landing craft were tested and adapted; tactics were developed from principles, tested, and revised. This went on in primitive conditions, as base housing and other facilities were at first non-existent, and then very basic. In time, the base established itself, and trained over 200,000 Naval and over 160,000 Army and Marine personnel.

All of these bases were partially inactivated at the end of World War Two, after being used for service separation, but the need for superior amphibious assault training was recognized, and a permanent base, Naval Amphibious Base Little Creek was established in 1946. Here, thousands of military personnel, Navy, Marine, Army, and members of allied foreign militaries have trained in modern amphibious assault.

In 2010, NAB Little Creek and Fort Story were merged as part of the 2005 BRAC, to help save administrative costs.