On his return, on 16 July 1491, he was elected among the three Wise Men in Rialto, but his undoubted ability as a seaman did not escape the Venetian governing bodies, which successfully employed him in risky operations.

In 1494, following the capture and hanging made by Loredan, near Zakynthos, of the pirate Bazuola, whose fleet flew the French flag, an envoy in the name of King Charles VIII arrived in Venice to ask for compensation of 80,000 ducats for damages caused.

Loredan carried out many other victorious enterprises in those years against pirates who infested the coasts of Tunisia, making the navigation for the Venetian merchant convoys safer.

In August he was ordered to join the Captain General of the Sea Melchiorre Trevisan to contain the hostile actions of the Turks who had taken the large galley of Alvise Zorzi.

Once there, Loredan presented himself, on 28 December, in front of the Senate, where he turned in an accurate report of his work and received public praise from Doge Agostino Barbarigo.

[1] As the new Duke of Corfu, the Senate ordered him to go, with his galleys, directly to the island without making stopovers and to immediately put himself in the service of Antonio Grimani, Captain General of the Sea.

When captain Albano d'Armer was the first to attack the most imposing Turkish ship, Loredan followed him and the three boats were chained together, starting a battle that lasted more than half a day.

During the most critical stage of the battle, two Venetian carracks, captained by Andrea Loredan and by Albano d'Armer, boarded one of the command ships of the Ottoman fleet.