L'edificio a pianta basilicale, significativo esempio dello stile veneto-bizantino, sorge appena discosto da quanto rimane della piazza dell'antica città e quasi isolata nel mezzo dell'isola. Accanto si trovano la chiesa di Santa Fosca e le fondazioni del battistero dedicato a San Giovanni, oggi scomparso: i tre edifici costituivano un unico complesso religioso. Il campanile si erge solitario poco distante e costituisce uno dei caratteristici punti di riferimento nella zona settentrionale della laguna. Nella stessa piazza si affacciano anche i due edifici storici Palazzo del Consiglio e Palazzo dell'Archivio, sedi del Museo provinciale di Torcello. Ha la dignità di basilica minore.

Il complesso basilicale presenta il tipico schema paleocristiano: il nucleo centrale è costituito dalla basilica, preceduta da un nartece, sul quale si innestava un tempo il battistero, del quale rimangono oggi solo le tracce, mentre sul fianco si erge tutt'oggi il martyrion, dedicato a Santa Fosca. Connesso al complesso, doveva infine un tempo sorgere il Palazzo Vescovile.

La facciata è composta di 12 lesene, collegate in alto da archetti a tutto sesto: il nartece, dell'XI secolo, è stato ampliato e modificato nel XIII secolo. Al centro, è il portale di marmo con stipiti del Mille. Il campanile è nel prato, con canna a lesene e cella campanaria a quadrifore. Il piccolo oratorio poco distante sorge sul luogo della chiesa di San Marco, eretta, secondo la tradizione, da Rustico da Torcello, uno dei due mercanti veneziani che, nell'Alessandria d'Egitto occupata dagli arabi, sottrassero le spoglie di San Marco Evangelista e le portarono in patria.

Si accede per la porta laterale destra. L’interno è diviso in tre navate da 18 colonne di marmo greco, con capitelli in stile corinzio. La controfacciata è interamente occupata da un mosaico in stile veneto-bizantino, raffigurante il Giudizio Universale: le schiere delle anime sono sovrastate in alto dalla figura di Gesù, tra Maria e Giovanni. Il presbiterio è separato dalle navate attraverso un’iconostasi, formata nella parte alta da sottili colonne marmoree con capitelli bizantini e, in basso, da bassorilievi di pavoni e leoni e da una serie di tavole lignee con immagini sacre. Al centro dell'abside si erge l'altare maggiore, ricostruito nel 1923 con le parti originarie: racchiude le spoglie di Sant'Eliodoro, primo vescovo di Altino. A sinistra dell’altare un'iscrizione su pietra, risalente alla fondazione della chiesa, costituisce il primo documento di storia veneziana.