The Museum originated as the Naval School Lyceum, established in 1845 under the Academy's first chaplain.  The Lyceum was a collection of historic and natural objects, scientific models and apparatus, and works of art brought together 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. Other trophies of war, of exploring and survey expeditions, and diplomatic missions, as well as works of art donated by naval officers were forwarded by the Navy Department after the Civil War.  The early collections of ordnance and ship models were used as teaching aids in the Academy's Departments of Gunnery and Seamanship.

In 1888 the U. S. Naval Lyceum at the New York Navy Yard was
disbanded, and its large collection of objects was transferred to the
Naval Academy.  The Academy also received the extensive collection of the Boston Naval Library and Institute in 1921.  Since the construction of a permanent museum building in 1939, many private individuals and groups have contributed important and valuable historic objects.

The Naval Academy Lyceum of the 19th century was located in a room over the mess hall, and later moved to a former chapel.  About 1910, exhibits were installed in Memorial Hall of Bancroft Hall. In 1920, Assistant Secretary of the Navy, Franklin D. Roosevelt recommended that the collections be placed in a "museum," and the ground floor of Maury Hall was made available for that purpose. Through the generosity of two private organizations, the Naval Academy Athletic Association and the U. S. Naval Institute, the present museum building was constructed and opened in 1939. The Naval Institute funded an addition in 1962, and in 1970 the entire building was formally dedicated to the memory of Commodore Edward Preble (1761-1807), an officer of the Quasi and Barbary Wars.