Budowę pałacu rozpoczął w 1451 r. Papież Paweł II Barbo, kiedy był tytularnym kardynałem pobliskiej bazyliki S. Marco i kontynuował ją w 1464 r., Gdy został wybrany na papieża. Praca została później wykonana przez jego bratanka Marco Barbo.

Projekt budynku, typowy dla XV-wiecznych pałaców rzymskich szlachciców, ukazuje wpływy Toskanii, zwłaszcza na „loggia delle benedizioni” i na niepełną loggię z widokiem na dziedziniec. Kiedy stał się własnością Lorenzo Cibo, bratanka papieża Innocentego VIII, budynek został powiększony wzdłuż del Plebiscito. W XVIII wieku kardynał Querini ma przejście wartownicze z widokiem przez pokryte degli Astalli, tworząc tzw. „Korytarz kardynałów”.

W 1911 r., aby zapewnić miejsce dla pomnika Wiktora Emanuela II po drugiej stronie Piazza Venezia, cała „szklarnia” Pawła II, która osiadła na głównej perspektywie, została przeniesiona i zrekonstruowana z całym jej kamienie, marmur i krużganki po lewej stronie budynku.

Palazzo Venezia zostało wyznaczone jako siedziba muzeum w 1916 r., kiedy to weszło w posiadanie państwa włoskiego, po tym jak służyło jako ambasada Republiki Weneckiej i spóźniło się z rasą austriackiej ambasady. Od 1929 do 1943 r. Został wybrany przez Mussoliniego jako rezydencja szefa rządu i Wielkiej Rady Faszyzmu.

Dziś w pałacu mieści się muzeum o tej samej nazwie. Warto zauważyć, że w budynku znajduje się Bazylika S. Marco, aw rogu między Palazzo i Palazzetto znajduje się jeden ze słynnych pomników Rzymu „Madama Lucrezia”.