L'edificio veneto-bizantino (in forma basilicale romanica) si presenta a tre navate, con pietre a vista, una facciata centrale sopraelevata scandita da sei lesene e un porticato antistante. Questo, originariamente sorretto da quattro colonne, ne vide aggiungersi altre da entrambi i lati, che lo portarono a congiungersi con quello di Santa Fosca nel corso del XIV e XV secolo.
Sul lato destro si erge la grande torre quadrata del campanile (XII secolo), emblema, come nelle contemporanee Pomposa e Aquileia, della potenza della città.
Anticamente la facciata era affiancata da un battistero a pianta circolare di cui ancora si possono vedere le fondamenta.
Sul fianco della chiesa sono interessanti le chiusure delle finestre centinate a grandi lastroni di pietra movibili su cardini anch'essi di pietra.
Il soffitto ligneo, ad incavallature scoperte, è rimasto forse quello originario.
L'ampia e luminosa navata tripla, con le alte colonne che sorreggono capitelli in parte romani e in parte imitati nelle officine veneziane, ricorda Sant'Apollinare Nuovo a Ravenna.
Il pavimento in mosaico di marmo è sopraelevato di circa venti centimetri sul preesistente del IX secolo, lavorato con cubetti bianchi e neri i cui resti si possono ammirare attraverso due botole.
Il presbiterio, ai cui piedi è posta la pietra tombale del vescovo Paolo di Altino, è segnato dall'iconostasi con al centro la porta sacra, delimitata da tre sottili colonne, chiuse per metà da plutei marmorei bizantini dell'XI secolo, adorni, come merletti di pietra, da immagini di fiori, leoni e pavoni che si abbeverano alla fontana divina. Le colonne sorreggono tavole quattrocentesche che rappresentano la Madonna attorniata dai dodici apostoli, su cui si innalza il coevo crocifisso ligneo.
L'altare, il cui piano è di spesso marmo greco, è stato ricostruito nel 1939 in luogo di un deturpante impianto barocco. Ai suoi piedi, protetto da una grata, si trova un sarcofago romano del III secolo che contiene le spoglie del santo vescovo altinate Eliodoro (spoglie traslate a Torcello in seguito alla conquista di Altino da parte dei Longobardi).
La conca absidale si apre con il trono del vescovo addossato all'abside, come in Santa Maria delle Grazie a Grado (V secolo). Questo si erge su gradinate circolari e vi si accede salendo dieci scalini, simbolo dei dieci comandamenti.
Sopra il trono episcopale è rappresentato, a mosaico, Sant'Eliodoro. Gli apostoli, vestiti con il proprio simbolo come nelle chiese ravennati, procedono simmetricamente sotto i piedi della Vergine. Al centro della processione si apre una finestrella, simbolo della luce divina, e la Vergine bizantina Teotoga (XII secolo), regalmente vestita e isolata nello spazio dorato del catino absidale, rappresenta l'incontro tra l'umano e il divino.
Tre le sue braccia regge il Bambino, che porta il rotolo della legge, mentre dalle sue mani pende un fazzoletto bianco, simbolo della mater dolorosa.
Il loro sguardo dolcissimo rapisce l'osservatore.
L'abside della cappella laterale destra, decorata a mosaico nel IX secolo e rimaneggiata nel XII secolo, rappresenta quattro dottori della Chiesa: Agostino, Ambrogio, Martino e Gregorio. Sopra è il Cristo Pantocratore con la tavola delle leggi attorniato dagli arcangeli Michele e Gabriele.
Nella cappella laterale sinistra permangono resti di un affresco duecentesco, e sulla stessa navata trova posto la piccola pala di Maria Vergine dipinta da Tintoretto.
L'imponente mosaico del Giudizio universale (XI - XII secolo), che occupa l'intera parete ovest (controfacciata), doveva ricordare ai fedeli che uscivano dalla funzione il destino finale.
Il racconto articolato in sei sequenze si legge dall'alto verso il basso: dalla Crocifissione alla separazione degli eletti dai dannati. Proprio nella raffigurazione di questi ultimi vi è la ricerca di un carattere narrativo più naturalistico, intensamente espressivo e radicalmente veneto: lo stesso carattere che si ritroverà nella Basilica di San Marco dove i mosaicisti si trasferirono alla fine di questo imponente lavoro.
