Die Kirche der Heiligen Apostel wurde in der Spätantike (4. Jahrhundert) an der Via Postumia (heute Corso Cavour) gegründet und weist die gleiche Ost-West-Ausrichtung wie der Decumanus von der Porta Borsari auf. Ihre Fassade ist noch immer in Richtung des Tors ausgerichtet. Die alte Kirche, die möglicherweise im 5. Jahrhundert renoviert wurde, zeichnete sich durch die Verbindung mit dem kreuzförmigen Sakellum aus, in dem die Reliquien der Märtyrerinnen Teuteria und Tosca aufbewahrt wurden und das noch heute neben der Apsis existiert. Der Grundriss der Kirche und der Kapelle folgte einem Schema, das auch in anderen zeitgenössischen Kirchen Venetiens zu beobachten ist, beispielsweise in Santa Giustina in Padua mit dem Oratorium San Prosdocimo oder in den Heiligen Felice und Fortunato in Vicenza mit dem Oratorium Santa Maria Mater Domini. Die Kirche wurde im zweiten Jahrzehnt des 12. Jahrhunderts mit drei Schiffen wieder aufgebaut und möglicherweise bereits im Spätmittelalter erneut umgebaut, wobei die Außenmauern erhöht wurden. Im unteren Teil der Mauern ist die für die Veroneser Romanik typische Verkleidung aus abwechselnd angeordneten Steinquadern und Ziegelsteinen zu sehen. Die durch Halbsäulen auf Lisenen mit korinthischen Kapitellen gegliederte Apsis erinnert an die Beispiele von San Fermo Maggiore und der Kathedrale. In der Kirche befinden sich mittelalterliche Fresken, darunter eines aus dem Ende des 12. Jahrhunderts zwischen Kirche und Sakristei, das zwei Frauen mit einem Palmzweig zeigt, die vor einem mit Edelsteinen besetzten Kreuz knien. Die über den Figuren eingetragenen Namen Paribella und Walda wurden als zwei fromme Frauen identifiziert, die mit der Kirche in Verbindung standen. Das Innere der Kirche Santi Apostoli, das in einen großen, einzigen Saal umgewandelt wurde, zeigt die Form, die es im 19. Jahrhundert angenommen hat.