Marco Gradenigo was a 13th-century Venetian nobleman, senior provincial administrator in the Venetian overseas empire and a military commander. 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). 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. As Villehardouin's forces recovered Negroponte, Marco Gradenigo laid siege to the city, an affair which dragged on for thirteen months before the city capitulated. An Achaean counterattack was repulsed by Venetian pike-wielding infantry sallying forth and defeating the famed Achaean cavalry before the city's walls.
By June 1256, Marco Gradenigo replaced Paolo Gradenigo as the resident Venetian governor (Bailo of Negroponte). In this capacity, he organized an alliance with the triarchs against the hegemonic claims of Villehardouin. Many other rulers of Latin Greece, including the Duke of Athens, Guy I de la Roche, joined this anti-Achaean league. Ultimately, the alliance failed, as Villehardouin defeated the allied forces at the Battle of Karydi in May/June 1258, resulting in a negotiated end to the war in 1259. By August 1258, Gradenigo had been replaced by Andrea Barozzi, and was appointed as Podestà of Constantinople, governor of the Venetian colony in Constantinople, capital of the Latin Empire.
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. His absence from Constantinople allowed the recapture of the city by the Nicaean general Alexios Strategopoulos. The Venetian fleet returned from it unsuccessful attack on Daphnousia only to find the city taken, the Venetian quarter in flames, and the Latin population fleeing. Gradenigo decided not to risk a landing, but instead took on the refugees, including the Latin Emperor, Baldwin II, and brought them to safety in Negroponte.
In 1264–1266, Gradenigo held naval commands in the conflict against the Republic of Genoa, and led a squadron of ten galleys under Jacopo Dondulo in the crushing Venetian victory at the Battle of Trapani in June 1266. In 1269, he was a ducal councillor. In 1270, he served as one of the two Venetian commanders in the war with Bologna in 1270. In 1272, he served again as ducal councillor.