Emperor Paul I, General-Admiral of the Russian fleet since early youth, openly criticized Catherine II's decisions regarding the navy. After ascending the throne, he changed practically everything in the Russian Navy, beginning with the uniform. An officer's full-dress uniform became more modest, dark-green instead of white and without gold braid. Strict observance of this new uniform soon became law. Fighting vessels were painted black and white and important alterations were introduced into ship construction. Quarterdecks were connected to forecastles by means of a through-deck and hulls became more spacious. On 1 January 1798, new staffs were confirmed and the fleet was officially divided: 45 ships of the line were stationed in the Baltic and fifteen in the Black Sea. The fleets were supplemented by 29 frigates, nineteen and ten respectively, as well as numerous rowing fleets, which, for the most part, consisted of gunboats.

That same year new navigation schools were established to replace the "navigator's companies," and in St. Petersburg and Nikolayev maritime academies were opened for shipbuilding and design.

In 1798, the winds of politics being unpredictable, Russia and Turkey became unlikely allies after the French seized Malta and Napoleon began his Egyptian campaign. According to the treaty between Russia and Turkey, the Russian fleet was granted the right to pass freely through the Bosporus into the Mediterranean. This allowed Vice-Admiral Fyodor Ushakov's squadron to pass through the Dardanelles and, after joining the naval forces of the Turkish Admiral Kadyr Bey, to head for the French-occupied Ionian Islands. The allied fleet numbered ten ships of the line (including four Turkish), five Russian and four Turkish frigates, and three Russian and eight Turkish small craft. Not long afterward, two ships of the line from the Black Sea Fleet and three ships of the line and a frigate from the Baltic Fleet joined Ushakov. From September to November, detachments of Ushakov's fleet seized, one after another, French fortifications on the islands of Cerigo, Zante, Cephalonia, and Saint Mauro. In addition, the Russian fleet successfully blockaded a key enemy position, the fortress on Corfu.

During this time a separate detachment of four frigates and ten gunboats, under Commander Alexander Sorokin, joined the British fleet off the coast of Egypt. Ushakov made a landing on Corfu and delivered the first blow to Vido Island. On the morning of 18 February 1799, after a signal from the 84-gun flagship Svyatoy Pavel [St. Paul], seven ships of the line and ten frigates bombarded the island's coastal batteries. The batteries were seized, and 2,000 assault troops stormed the island, capturing 422 French troops. The damaged 54-gun enemy ship Leander retreated to the walls of the citadel. On the same day the Russian-Turkish force stormed the first group of forts on Corfu. The situation became hopeless for the French, and the Šommandant hoisted a white flag. The Russian victors captured 636 guns and mortars, the Leander, the frigate La Bruin and 14 small craft. All 2,931 defenders of the garrison were taken prisoner.

The Allies had scored an important victory, and the Russian fleet now possessed a strategically located base in the Mediterranean. Ships were immediately dispatched from Corfu to attack French supply routes and assist Allied forces in Italy. In only nine days Sorokin's detachment took the towns of Brindisi, Mola and Bari, and Vice-Admiral Pavel Pustoshkin's squadron blockaded Ancona.

On 9 May in Italy, Sorokin landed an assault force under the command of Lieutenant-Commander Grigory Belli, captain of the frigate Shchastlivy. Belli's detachment, though containing only 547 men and 6 guns, played an important role in the ensuing battles. On 3 June 1799, the Russian force joined with the Naples troops in the liberation of Naples. In September Ushakov arrived, having left Captain Voinovich in command of the blockade of Ancona and Vice-Admiral Pustoshkin to command the blockade of Genoa.

After Naples and Ancona, the Russian goal was Malta, which was under siege by the British without any noticeable success. Although Great Britain was Russia's ally against Napoleon, the English were concerned about the Russian fleet's growing strength in the Mediterranean. England was especially troubled by Russia's newly-attained strategic position in the Ionian Islands. In addition, Britain refused to recognize the Order of the Knights of St. John of Jerusalem on the island of Malta, the Grand Master of which was Emperor Paul I. The British began to delay operations on Malta, not accepting Russia's offer of assistance. Although Russia had no plans for involvement in the Egyptian campaign, Vice-Admiral Horatio Nelson, commander of the British squadron, even attempted to dispatch Ushakov and his Russian forces to Egypt. A compromise was reached, and it was decided to send the squadron of Vice-Admiral Victor Kartsov. Ushakov was senior to Nelson in rank, and in the anticipated operations on Malta the British would have to follow the Russian officer's orders, an arrangement that further rankled the British.

In any event, the Malta campaign did not materialize. In late December 1799, Ushakov received an order to cease action in the Mediterranean and return with his fleet to the Black Sea. Only a few Russian vessels remained on Corfu, while the Ionian Islands became a republic under Russian control.