In 1845, the Museum began as the Naval School Lyceum, established under the Academy's first chaplain. The Lyceum brought together a collection of historic and natural objects, scientific equipment and models, and works of art for study and discussion. In 1849, President James K. Polk directed that the Navy's collection of historic flags be sent to the new Naval School at Annapolis for care and display. After the Civil War, the Navy Department forwarded trophies of war, items from exploration and survey expeditions, as well as diplomatic missions, and works of art donated by naval officers. The Academy's Gunnery and Seamanship Departments used the Lyceum's early collections of ordnance and ship models as teaching aids.
Over the next sixty years, the Lyceum and its collection grew significantly. This was primarily due to the transfer of of the collections of the U. S. Naval Lyceum at the New York Navy Yard in 1892 and the receipt of the extensive collection of the Boston Naval Library and Institute in 1922. Since 1939, many private individuals and groups have contributed important and valuable historic objects.
The Naval Academy Lyceum of the 19th century was first located in a room over the mess hall, but moved into a former chapel in the late 1860s. Around 1910, exhibits were installed in Memorial Hall of Bancroft Hall. In 1920, Assistant Secretary of the Navy, Franklin D. Roosevelt recommended that the Lyceum's collections be placed in a "museum." The ground floor of Maury Hall was then made available for the Lyceum. The present museum building was constructed and opened in 1939 through the generosity of two private organizations, the Naval Academy Athletic Association and the U. S. Naval Institute. The Naval Institute funded an addition to the building in 1962 and in 1970 the entire building was dedicated to Commodore Edward Preble (1761-1807), an officer of the Revolution, Quasi War with France, and Barbary Wars.
From 2007-2008, Preble Hall underwent a complete renovation to turn the building into a modern museum. New exhibits, improved collections storage areas, and upgraded office space were some of the updates made to the space. The museum officially reopened in the summer of 2009.