Secondo la tradizione, Sant'Efisio nacque a Elìa Capitolina, una colonia romana nel seno di Gerusalemme, attorno al 250 d.C. Rimasto orfano del padre Cristoforo, di religione cristiana, fu educato al paganesimo dalla madre Alessandra, di origine aristocratica. Alessandra introdusse il figlio alla corte di Antiochia, presso l'imperatore Diocleziano, il quale lo prese sotto la sua protezione. Efisio si arruolò fra i Pretoriani, diventò ufficiale e fu inviato in Italia per partecipare alla campagna di annientamento dei Cristiani, considerati nemici dello Stato e della legge romana. Qui il giovane ufficiale visse un episodio che cambiò il corso della sua vita: mentre era in marcia verso Napoli (o Brindisi) alla testa del suo reparto, venne disarcionato da un bagliore improvviso. Quindi una voce gli disse: "Sono il Cristo, colui che tu perseguiti". E sul palmo della sua mano destra si impresse una croce.
In seguito a questo evento prodigioso Efisio decise di convertirsi alla fede cristiana e si fece battezzare a Gaeta. Quindi venne trasferito in Sardegna per contrastare gli Iliesi, le popolazioni ribelli dell'interno: prima prese servizio a Tharros, quindi presso il comando militare di Nora. Nonostante gli editti anticristiani emanati da Diocleziano, Efisio cominciò a diffondere pubblicamente il Vangelo e radunò attorno a sé un gruppo di seguaci. Non solo: scrisse all'imperatore e lo esortò ad abbandonare i falsi dei e a convertirsi alla nuova religione. Per questo motivo venne convocato a Cagliari presso il governatore Iulio, il quale gli intimò di tornare nei ranghi.
Efisio rifiutò decisamente di abiurare la fede cristiana, atto che obbligò il governatore ad arrestarlo e imprigionarlo in una cella ricavata da una caverna, nel luogo in cui oggi sorge la chiesa a lui dedicata a Stampace. Qui venne flagellato, bastonato, scarnificato e bruciato con tizzoni ardenti. Tuttavia, né le torture, né la madre Alessandra fatta intervenire dalla corte imperiale, riuscirono a farlo recedere.
Il nuovo governatore Flaviano ordinò che Efisio fosse bruciato vivo quale esempio per tutti i Cristiani, ma le fiamme del rogo si riversarono sugli stessi carnefici. Allora Flaviano dispose la decapitazione per spada, da eseguirsi lontano dalla città per timore di insurrezioni a difesa del martire. La condanna fu eseguita sulla spiaggia di Nora il 15 gennaio del 286 (o, secondo altre fonti, nel 303).
Si tramanda che prima dell'esecuzione Efisio abbia formulato questa preghiera:
"Ti prego, Signore, di proteggere la città di Cagliari dall'invasione dei nemici. Fa che il suo popolo abbandoni il culto degli Dei, respinga gli inganni del Demonio e riconosca Te, Gesù Cristo Nostro Signore, quale unico vero Dio. Fa che i malati che pregheranno sul luogo della mia sepoltura possano recuperare la salute, e chiunque si trovi in pericolo nel mare o minacciato dagli invasori, tormentato dalla fame o dalla peste, dopo aver invocato me, Tuo servo, possa essere condotto in salvo."