L’église des Saints-Apôtres fut fondée à la fin de l’Antiquité, au IVᵉ siècle, le long de la via Postumia (actuellement, corso Cavour), avec la même orientation est-ouest que le decumanus provenant de la Porta Borsari. Sa façade est encore aujourd’hui tournée vers ceux qui se dirigent vers cette porte. L’église primitive, probablement remaniée au Vᵉ siècle, se distinguait par sa connexion avec un sacellum à plan cruciforme, destiné à conserver les reliques des martyres Teuteria et Tosca, encore visible sur le côté de l’abside. L’ensemble formé par l’église et le sacellum suivait un schéma répandu dans d’autres édifices contemporains de la Vénétie, comme Santa Giustina à Padoue avec l’oratoire de San Prosdocimo, ou les églises des saints Félix et Fortunat à Vicence avec l’oratoire de Santa Maria Mater Domini. L’église fut reconstruite à trois nefs au début du XIIᵉ siècle, puis de nouveau modifiée, probablement dès le bas Moyen Âge, par l’élévation des murs périmétraux. Dans la partie inférieure des parois, on observe le parement typique du roman véronais, alternant assises de pierre et de briques. L’abside, rythmée par des demi-colonnes adossées à des lésènes et surmontées de chapiteaux corinthiens, rappelle les modèles de San Fermo Maggiore et de la cathédrale de Vérone. L’église conserve plusieurs fresques médiévales, dont l’une, datant de la fin du XIIᵉ siècle et située entre l’église et la sacristie, représente deux femmes tenant une palme, agenouillées devant une croix ornée de pierres précieuses. Les noms inscrits au-dessus des figures, Paribella et Walda, ont été identifiés comme ceux de deux fidèles de la communauté. L’intérieur de l’église, transformé en une vaste salle unique, est aujourd’hui visible dans la configuration adoptée au XIXᵉ siècle.