L'edificio — dedicato alle quattro vergini di Aquileia: Eufemia, Dorotea, Tecla ed Erasma rese martiri dall'imperatore romano Nerone — rappresenta la costruzione più antica della Giudecca e una delle più datate di Venezia.
Pare esser stata costruita, per la prima volta, nell'865 e — tra le varie sistemazioni — venne rifabbricata nel 1100. Nel 1380, le spoglie delle martiri, precedentemente deposte a Grado per 400 anni, vennero posizionate sotto all'altare maggiore.
Oltre a questa ristrutturazione, la chiesa subì altre modificazioni nel Seicento e nel Settecento, ed oggi la ritroviamo con una pianta basilicale a tre navate suddivise da due colonnati con belli e antichi capitelli del XI secolo; la facciata, semplice e spoglia a capanna, è tripartita da due lesene ed illuminata da finestre semicircolari. Il portale è sormontato da un bassorilievo raffigurante La Vergine col Bambino tra San Rocco e Sant'Eufemia attribuito allo scultore Bregno.
Alla destra della chiesa, è presente un portico architravato mentre dietro è presente un campanile alto all'incirca 20 metri.