She served in the North Sea and the Baltic until the British 74-gun third rates Implacable and Centaur destroyed her in 1808 during the Anglo-Russian War (1807–1812).

On 3 July 1798 Vsevolod was at Arkhangel’sk, serving as flagship for Vice-Adm. Thate, who commanded the 2nd Division of the Imperial Russian Navy.

[1] In early 1808 Russia initiated the Finnish War in response to Sweden's refusal to bow to Russian pressure to join the anti-British alliance.

The Swedes massed a fleet under Swedish Admiral Rudolf Cederström, consisting of 11 line-of-battle ships and 5 frigates at Örö and Jungfrusund to oppose them.

On 22 August, the Russian fleet, consisting of nine ships of the line, five large frigates and six smaller ones, moved from Hanko to threaten the Swedes.

13 August] Vsevolod, under Captain Rudno (or Rudnew or Roodneff) exchanged fire with Implacable, with the Russian suffering heavy casualties before running aground.

During the fight Implacable lost six men killed and twenty-six wounded, including two who did not recover and three who had limbs amputated.

15 August] the British removed their prisoners, including the wounded, and then set fire to Vsevolod, which blew up some hours later.

The court martial ordered Khanykov demoted to the rank of Ordinary Seaman for one day and dismissed from the service.

His Swedish Majesty Gustaf IV Adolf conferred upon Captain Martin of Implacable the Knight Grand Cross of the Order of the Sword.