Согласно «Мученичеству...», мощи Киприана и Иустины вскоре после гибели святых были привезены в Рим моряками, и там матрона Руфина построила в их честь храм у форума Клавдия. Некоторые исследователи считают эти сведения достоверными, но данные о почитании мощей Киприана и Иустины в Риме раньше XII в. отсутствуют. В эпитафии нотария Евгения и его родственников 577–578 гг., обнаруженной в Ватиканской базилике, упоминается церковь св. Киприана на Лабиканской дороге (лат. iuxta sanctum Cyprianum uia Labicana), однако этот храм, скорее всего, как полагают исследователи, носил имя Киприана Карфагенского. В «Книге о Латеранской церкви» в редакции Иоанна Диакона (вторая половина XII в.) сообщается о двух алтарях в нартексе Латеранского баптистерия, освящённых папой Римским Анастасием IV (1153–1154 гг.). При сооружении алтаря во имя святых Руфины и Секунды были обнаружены мощи не только этих мучениц, но и Киприана и Иустины. Обретённые мощи Киприана и Иустины были помещены в алтарь, освящённый в день их памяти, т.е. 26 сентября. По мнению болландистов, мощи четырёх названных мучеников первоначально почивали в базилике святых Руфины и Секунды на Корнелиевой дороге (с названием храма связано имя матроны Руфины, зафиксированное в агиографической легенде). К XII в. пригородная базилика начала разрушаться, хранившиеся там святыни были перенесены в Латеран и по указанию папы Анастасия IV помещены в соответствующие алтари. В настоящее время мощи Киприана и Иустины хранятся внутри барочного алтаря, освящённого в 1727 г. Кроме Латеранской базилики почитание Киприана и Иустины в Средние века засвидетельствовано в других римских храмах, в том числе в базилике Санта-Мария-Маджоре. В Константинополе существовал мартирий Киприана и Иустины в квартале Соломонос, где могли храниться мощи святых. Русские паломники Стефан Новгородец (в 1348–1349 гг.) и диакон Зосима (в 1419–1422 гг.) поклонялись мощам Киприана, которые находились в посвящённом ему монастыре в восточной части Константинополя. Исследователи полагают, что к XIV в. эти мощи были перенесены на новое место из старого мартирия. В «Хронике» Леонтия Махераса (середина XV в.) сообщается, что главы Киприана и об Иустины хранятся на Кипре, в деревне Менико, куда они были принесены из Антиохии (там же находится источник с целебной водой). Частицы глав и другие части мощей до сих пор сохраняются в деревне Менико в храме во имя Киприана и являются одними из самых почитаемых святынь на Кипре. В иконостасе этого храма есть чудотворная икона Киприана XVII в. В 2005 г. частицы мощей привозились на поклонение в Москву, в Зачатиевский монастырь. Частицы мощей Киприана и Иустины хранятся и на Афоне, в монастырях Иверском и Ксенофонт, а также в Каламате, Патрах и других городах Греции.