Originally commissioned by the East German People's Navy as the Rudolf Eglehofer, the Hiddensee is a Tarantul I class corvette built at the Petrovsky Shipyard, located near the Soviet city of St. Petersburg (formerly Leningrad). The world's only exhibited example of a Soviet-built missile corvette, Hiddensee was designed to oppose any naval threat to the East German Coast, and to fulfill this mission carried long-range STYX anti-ship missiles and an array of defensive weapons designed to ensure her own survivability.
Following the reunification of Germany, the Hiddensee served with the Federal German Navy until her decommissioning in April 1991. Shortly thereafter she was reactivated and transferred to the U.S. Navy. Joined briefly by a crew of 20 former East German sailors, a small civilian U. S. crew conducted extensive testing with the vessel at the Navy's Solomons, Maryland, facility in the Patuxent River. After 50 underway deployments in the Chesapeake Bay and Virginia Capes areas, Navy budget cutback severely curtailed operations, but she continued on as a research vessel until April 1996.
The Hiddensee joined the Battleship Cove fleet on June 14, 1997.