Il Palazzo nacque come casa "fontego" di evidente gusto tardogotico. Il primo nucleo dell'edificio risale infatti al 1300 e fu scelto dai nobili Contarini del ramo di San Paternian come residenza di famiglia grazie alla posizione strategica occupata dall'edificio, equidistante da Rialto – luogo di commercio – e da San Marco – centro del potere politico veneziano. Nel 1499 Pietro Contarini commissionò la splendida e aggraziata scala a chiocciola (il "bovolo" in veneziano) per "abbellire" ulteriormente questo lato del palazzo, già di per sé riccamente affrescato con motivi floreali, di cui oggi rimangono solo pochi frammenti di affresco. La paternità di questa imponente opera architettonica è ancora sconosciuta. Alcuni storici lo attribuiscono al capomastro locale Giovanni Candi, altri suggeriscono il nome dell'architetto Giorgio Spavento.

Il manufatto è formato da una spirale di gradini che si sviluppa all'interno di una torre cilindrica alta 26 metri, costruita in pietra d'Istria e mattoni a vista, traforata da una serie di archi e fiancheggiata da logge che la collegano all'edificio adiacente.