Obecny kościół Budowę obecnego kościoła i klasztoru z jego fasadą wychodzącą pierwotnie na Campazzo San Sebastiano (według mapy De Barbariego z 1500 roku), a obecnie na kanał Rio de San Sebastian, zrealizował w latach 1506–1548 Antonio Abbondi, znany jako Scarpagnino. Fasada kościoła została wyłożona kamieniem z Istrii. W 1562 roku miała miejsce jego druga konsekracja. W latach 1555–1581 na zlecenie przeora Bernarda Torlioniego ściany i sklepienie kościoła pokrył malowidłami Paolo Veronese. Według popularnej lokalnej legendy, Veronese miał znaleźć schronienie w kościele San Sebastiano w 1555 roku po ucieczce z Werony przed zarzutem morderstwa. Wykonane przez niego prace w kościele stały się wyrazem jego wdzięczności dla parafii i powodem do zawiści w oczach jego oskarżycieli. Po śmierci Veronese został w kościele San Sebastiano pochowany.
Malowidła, mające w zamyśle zleceniodawcy stanowić alegorię triumfu wiary nad herezją, Veronese wykonał w trzech etapach: w pierwszym, zrealizowanym w latach 1555–1556, udekorował strop zakrystii scenami ze Starego Testamentu, po czym wykonał kompleksową dekorację kasetonowego stropu kościoła, inspirowaną Księgą Estery.