Euphemia ging der Legende nach als Senatorentochter aus Rom zum Richter Priscus in Chalcedon - heute der Stadtteil Kadıköy in Ístanbul -, bekannte sich öffentlich zum Christentum und stärkte alle von der Diokletianischen Verfolgung Betroffenen. Vor ihren Augen ließ Priscus alle enthaupten, aber sie wurde dadurch nur noch mutiger und warf ihm sein Unrecht vor. Geschlagen und ins Gefängnis geworfen, wollte ihr der Richter Gewalt antun, da verdorrte seine Hand. Der Hausmeister sollte sie überreden, aber es gelang ihm weder, die Tür aufzuschließen, noch, sie mit dem Beil zu zertrümmern, er wurde darüber besessen und tötete sich selbst. Auf ein eisernes Rad gebunden, das auf zum Glühen gebracht werden sollte, zersprang das Rad und zerriss den Werkmeister; nun schürten dessen Eltern das Feuer, aber ein Engel stellte Euphemia auf einen höheren Ort, wo sie von der Hitze verschont wurde, aber alle sie sehen konnten. Man legte eine Leiter an, um sie herabzuholen, aber Euphemia war von Engeln bewacht; einer der Folterer wurde gelähmt, ein anderer wurde irrsinnig und wollte sich selber umbringen.
Der Schreiber des Priscus sollte nun alle Lotterbuben der Stadt zu ihr ins Gefängnis führen; als er dann zur Kontrolle ins Gefängnis kam, sah er so viele leuchtende Jungfrauen um Euphemia stehen, dass er selbst gläubig wurde. Der Richter ließ Euphemia an den Haaren aufhängen, dann sieben Tage ohne Nahrung zwischen Steine pressen, aber die Steine zerfielen zu Staub, ein Engel ernährte sie. Zu wilden Tieren in die Grube geworfen, legten diese ihre Schwänze zusammen wie zu einem Stuhl, worauf sie ruhen konnte. Der Henker stürzte in die Grube, stieß ihr sein Schwert in die Seite, Euphemia starb und der Richter warf dem Henker zur Belohnung sein seidenes Kleid und einen goldenen Gürtel zu, doch ein Löwe erfasste und verschlang ihn, nur Knochen und der Gürtel wurden gefunden; der Richter zerfleischte sich selbst.
Euphemia wurde mit Ehren begraben, durch ihr Verdienst bekehrten sich alle Juden und Heiden von Chalcedon. Über ihrem Grab in Chalcedon - dem heutigen der Stadtteil Kadıköy in Ístanbul - wurde im 4. Jahrhundert eine prächtige Basilika erbaut, in der 451 das 4. ökumenische Konzil abgehalten wurde; das dabei von ihr geschehene Wunder hat in der Armenischen und in der Orthodoxen Kirche einen eigenen Gedenktag, weil dadurch die Orthodoxie bekräftigt wurde. Euphemias Reliquien wurden um 620 nach Konstantinopel - dem heutigen Ístanbul - gebracht. Um 800 kam der zuvor in Konstantinopel aufbewahrte Steinsarg mit Euphemias Reliquien nach Rovinj in Kroatien; die Legende erzählt, ein kleiner Junge habe am 13. Juli 800 den schweren Sarg, der vom Meer ans Land gespült worden sei, geborgen. Euphemias Gebeine wurden zunächst in der Georgs-Kirche in Rovinj aufbewahrt, ab 1720 wurde die heutige, Euphemia geweihte Kirche erbaut.
Euphemia wird zusammen mit Thekla von Ikonium in Triest besonders verehrt. Die dortige Überlieferung erzählt vom Martyrium der beiden im Jahr 256; über dem angeblichen Wohnhaus der beiden steht die aufs 9. Jahrhundert zurückgehende Kirche San Slvestro, die heute von den Waldensern genutzt wird.