È ricordato al 29 gennaio già dal Martirologio Geronimiano. Secondo la leggenda, di cui esistono quattro redazioni, fu tradotto davanti al console Lucio durante la persecuzione di Antonino e barbaramente flagellato, indi rinchiuso con altri compagni in una stufa ardente dalla quale uscì illeso. Ricondotto in carcere, convertì i suoi custodi che lo aiutarono a fuggire. Rifugiatosi in casa di un certo Anastasio cristiano, fu, insieme con questi, di nuovo arrestato. Dopo varie peripezie nelle carceri di Assisi e Spello, fu decapitato presso Foligno. Le diverse redazioni della passio sono concordi nello assegnare il suo martirio al tempo di Antonino in una località presso Foligno denominata "il Trivio". Il santo perugino aveva infatti in questa città, vicino a Porta Romana, una chiesa che, secondo lo Iacobilli, fu demolita nel 1527. Questi afferma inoltre che, al suo tempo, tale località era chiamata ancora "campagna di S. Costanzo".

Parimenti tutte le redazioni della passio affermano che il santo, dopo il martirio, fu portato a Perugia e sepolto non lontano dalla città in, un luogo detto "Areola fuori Porta S. Pietro", ove sorse la prima cattedrale di Perugia, dedicata al principe degli Apostoli. In questo medesimo luogo fu eretta l'attuale chiesa di S. Costanzo consacrata, secondo un'iscrizione esistente nell'antico altare, nel 1205 dal vescovo di Perugia Viviano. L'episcopato di Costanzo, secondo il Lanzoni ed il Delehaye, riposa su una tradizione antica e seria per cui si può ritenere assai probabile che egli sia stato il primo vescovo di Perugia. Il suo martirio risale alle persecuzioni dei primi secoli.

I perugini venerano in lui uno dei protettori della città. Il suo culto si diffuse anche fuori dell'Umbria. Nel 1781 fu fatta una ricognizione delle sue reliquie e nel 1825, con grande solennità, la traslazione delle medesime dal vecchio al nuovo altare, sempre nella attuale chiesa di S. Costanzo.