The Willemoes were a Danish-manufactured class of fast attack craft built for the naval defence of Denmark during the Cold War. The eighth of ten ships of her class, Sehested was built at Frederikshavn Shipyard.
The 46-metre 264-tonne ship was laid down 22 December 1976, launched on 5 May 1977 and commissioned into the Royal Danish Navy on 19 May 1978. She was armed with a 76 mm autocannon on the foredeck, flanked by two 5330NaN0 torpedo tubes. Six 1030NaN0 rocket launchers were fitted to the superstructure, and there were eight Harpoon anti-ship missile launchers at the stern. The ship also carried sixteen mines, two Stinger surface-to-air missiles and Seagnat chaff launchers. The maximum capacity of sixteen mines could only be fitted if the two 21-in torpedo tubes were removed and replaced by mine holders. If the torpedo tubes were in place, the mine capacity was limited to four mines.
If the four mine holders were removed, two additional 21-in torpedo tubes could be mounted, these tubes came preloaded, from the onshore arsenal, and could only be reloaded by dismounting them again. If four torpedo tubes were fitted, none of the tubes could be reloaded at a tender, aft tubes had to be dismounted.The vessel was powered by three Rolls-Royce Proteus gas turbine engines on the three shafts, while there were two GM 8V71 diesel engines on the outer two shafts only to provide low speed manoeuvrability.
In 1999, Sehested achieved a top speed of 42.5 knots, which were the highest recorded and documented speed ever achieved for the Willemoes-class.
The sharks teeth painted on the ship, were allowed by the squadron commander early 2000, due to the fate of the ship, the sister vessel Rodsten (P546), had crying eyes painted. In 2000, Rodsten won the Cannonball pennant, during the race from Kiel to Korsør Naval Base, with Sehested, thus being the last holder of the champion title.
In the 2000 Danish Defense Agreement it was decided to phase out the Willemoes-class, and Sehested was decommissioned on 31 December 2000. She was handed over to the Royal Danish Naval Museum and docked at the historic Holmen Naval Base in Copenhagen to serve as a museum ship.