He was involved in three major conflicts: the War of the Euboeote Succession, where Gradenigo organized a league of the lords of Latin Greece against the Principality of Achaea; the defence of the Latin Empire against the Empire of Nicaea, which failed with the Reconquest of Constantinople by the Nicaeans during Gradenigo's tenure as Podestà of Constantinople; and the naval operations of the War of Saint Sabas against the Republic of Genoa.
In December 1255, Marco Gradenigo was sent with three galleys (seven, according to Andrea Dandolo) to reinforce the Venetian garrison of the City of Negroponte (modern Chalkis).
[1][2] The city had been captured by the local Lombard lords of Euboea (the 'triarchs') with Venetian assistance, against the claims of the Prince of Achaea, William II of Villehardouin, thus sparking the War of the Euboeote Succession.
[2] In July 1261 Gradenigo led his fleet of thirty ships to capture the island of Daphnousia in the Black Sea, held by the Empire of Nicaea.
[2][7] In 1264–1266, Gradenigo held naval commands in the conflict against the Republic of Genoa,[8] and led a squadron of ten galleys under Jacopo Dondulo in the crushing Venetian victory at the Battle of Trapani in June 1266.