Paolino, racconta nella “Vita Ambrosii” che, ormai vicino al compimento della sua esistenza terrena, nel 395, il vescovo di Milano Ambrogio rinvenne in un cimitero fuori città i resti mortali del martire Nazaro, e li ripose nella basilica milanese dei santi Apostoli in Porta Romana, da lui stesso fatta edificare pochi anni prima. La basilica da quel momento prese il titolo del Santo martire. Poco dopo ritrovò nel medesimo luogo cimiteriale anche i resti del martire Celso, e gli dedicò in loco un sacello, che in seguito divenne una chiesa.
Il rinvenimento delle reliquie dei due martiri, della cui passione non si conserva alcuna notizia se non leggendaria, fu accompagnato da miracoli e grande movimento di devozione del popolo milanese. Insieme ai santi Gervaso e Protaso, ebbero subito un culto molto vivo, diffusosi anche nella Chiesa di Roma e nelle Chiese d’Oriente, e una ricca tradizione di testi liturgici.