I santi martiri Paolo e sua sorella Giuliana furono giustiziati sotto l'imperatore Aureliano (270-275) nella città fenicia di Tolemaida. Una volta l'imperatore ebbe occasione di recarsi a Tolemaida. Tra quelli che lo incontrarono c'era Paolo, che si fece il segno della croce, e questo fu notato. Lo arrestarono e lo gettarono in prigione. Il giorno successivo, quando lo processarono, confessò apertamente e coraggiosamente la sua fede in Cristo, per la quale fu sottoposto a feroci torture. Giuliana, vedendo la sofferenza del fratello, cominciò davanti a tutti a denunciare l'imperatore per la sua ingiustizia e crudeltà, per le quali fu anch'essa sottoposta a tortura. Picchiarono i martiri, strapparono i loro corpi con ganci di ferro, li bruciarono su grate arroventate, ma non riuscirono a spezzare la meravigliosa resistenza dei confessori del Signore. Tre soldati che torturavano i santi furono colpiti dallo spirito magnanimo dei martiri e credettero a loro volta in Cristo. Questi nuovi prescelti da Dio si chiamavano Quadrato, Acacio e Stratonico, e furono immediatamente giustiziati. Il carnefice cercò di sedurre santa Giuliana con la promessa di prenderla in sposa, se avesse rinunciato a Cristo, ma la santa rifiutò l'offerta del tentatore e rimase irremovibile. Per ordine dell'imperatore consegnarono la martire a una casa di malaffare perché fosse contaminata, ma il Signore la preservò anche lì: chiunque tentasse di toccare la santa perdeva la vista. Quindi l'imperatore infuriato ordinò che venissero nuovamente bruciati i corpi dei santi. La gente che si accalcava e vedeva la sofferenza dei santi cominciò a mormorare ad alta voce, e Aureliano diede ordine di decapitare immediatamente i martiri. Con volto lieto il fratello e la sorella si avviarono all'esecuzione cantando: «Poiché tu, il Signore, ci hai salvati dagli oppressori e hai svergognato quelli che ci odiavano» (Sal 43[44], 7).