Le origini della Chiesa di San Nicolò risalgono al 1044, quando venne edificata per volere del doge Domenico Contarini. Qui, intorno al 1100, furono trasportate dalla città di Myra, in Anatolia, alcune reliquie di San Nicolò, che presto divenne il patrono dei pescatori, dei naviganti e dei soldati diretti in Terrasanta.
La chiesa attuale fu edificata nel 1627 accanto a un preesistente monastero benedettino, convertito in epoca napoleonica in caserma militare. Intorno al 1940 furono riscoperti i capitelli corinzi "a palmette" delle colonne, databili intorno all'XI secolo, e murati con la conversione dell'edificio.
Tra gli anni '50 e '60 fu rinvenuto e restaurato anche un mosaico pavimentale a motivi geometrici e floreali dell'antica Basilica romanica. Oltre al coro con rilievi seicenteschi, raffiguranti scene della vita di San Nicolò, la chiesa conserva due importanti dipinti: una Madonna con il putto di Palma il Vecchio e un San Giovannino di Palma il Giovane.