Sul luogo di un oratorio dedicato a Maria Assunta, annesso a una modesta sede trecentesca di monaci Gerolamini, nasce nella seconda metà del Quattrocento una chiesa con l'intitolazione supplementare a San Sebastiano, che il leggendario santo delle frecce s'era guadagnata preservando gli abitanti della zona dalla terribile peste del 1464. Ma ben presto gli spazi della chiesa e del monastero risultano insufficienti alle esigenze della comunità, dal momento che nel gennaio 1506 si gettano le fondamenta di una nuova fabbrica, diretta da Antonio Abbondi, meglio noto come Scarpagnino, che si concluderà con la severa facciata soltanto nel 1548. Nel 1542 il priore dei Gerolamini, Bernardo Torlioni da Verona, chiama Scarpagnino a modificare in corso d'opera il progetto originario di ricostruzione a ristrutturazione della chiesa con l'inserimento di sei cappelle, tre su ogni lato, all'interno della navata. Lo scopo è evidentemente quello di garantire alle casse del convento un afflusso di denaro senza precedenti. Nessuna indulgenza papale, nessun appello alla devozione e alla pietà potevano stimolare la generosità dei fedeli quanto il diritto di sepoltura. Molte illustri famiglie veneziane erano pronte a finanziare la costruzione della loro cappella, ad arredare e decorare i loro altari, a contribuire largamente ai lavori della chiesa e del monastero, pur di sapere che i frati avrebbero in perpetuo celebrato messe in loro suffragio e pregato per la salute della loro anima. Visto che nel 1542 la chiesa era quasi ultimata e non c'erano lavori urgenti in cantiere, questa ricerca di nuovi fondi indica che Torlioni aveva già in mente il costoso progetto di decorazione pittorica dell'intera chiesa. La costruzione delle cappelle laterali non solo determina l'aspetto attuale della chiesa dal punto di vista architettonico, ma crea i presupposti finanziari perché questa diventi uno dei luoghi più rappresentativi dell'opera di Paolo Veronese, che con i suoi dipinti e le sue architetture reali e fittizie trasforma la sobria struttura ideata dallo Scarpagnino in un organismo ricco, articolato e colorato.