Это предание было широко распространено в Средние века. В подземелье существовала церковь Сан-Пьетро-ин-Карчере (буквально - "Святой Петр в тюрьме"), а над ней в XVI веке была возведена церковь Сан-Джузеппе-деи-Фаленьями. Археологи убедились, что уже к VIII веку темница была преобразована в церковь, причем преобразование тюрьмы в церковь произошло очень быстро.
Согласно преданию, святые апостолы Петр и Павел были брошены в Мамертинскую темницу во время так называемых Нероновых гонений на христиан. Утверждается, в частности, что они смогли чудесным образом открыть в темнице источник воды и крестили в нем тех, кто был заключен вместе с ними, а также стражников. Апостолы были казнены примерно в 64 году (по преданю, Павла обезглавили, а Петра распяли вниз головой, отчего и крест на алтаре в темнице "перевернут").
Мамертинская темница была сооружена в VII веке до Р.Х. Она была предназначена для временного содержания подследственных и подсудимых. Римское право не предусматривало наказания в виде тюремного заключения. Темница соединялась подземным каналом с Большой клоакой - римской канализацией, куда, по легенде, сбрасывали трупы умерших заключенных.
Среди знаменитых узников Мамертинской темницы, помимо святых Петра и Павла, называют пленного нумидийского царя Югурту (II век до нашей эры); кельтского вождя Верцингеторига, плененного Цезарем во время Галльской войны (I век до нашей эры), а также Публия Корнелия Лентула Суру, одного из главных участников так называемого заговора Катилины (I век до нашей эры) и опального командира преторианской гвардии Луция Элия Сеяна (I век нашей эры).