Имена Иоанна и Павла содержатся в древнейшем тексте римского канона мессы (в молитве «Communicantes et memoriam venerantes»), включённом в Сакраментарий Григория, а также в расширенной версии римской литании Всем святым, которая сформировалась в позднем Средневековье и была включена в тридентские богослужебные книги. После строительства базилики (V в.) о церкви св. мучеников Иоанна и Павла сохранилось много сведений. Исследователи полагают, что в V–VI вв. в храме собирались две христианские общины, имевшие своё духовенство; общины упоминаются в источниках как «титул Византа» и «титул Паммахия». Не позднее второй половины VI в. обе общины объединились в «титул святых Иоанна и Павла», хотя и в более позднее время иногда употреблялись прежние названия. В сборнике папских эпитафий и надписей из римских церквей приведены тексты стихотворных надписей, посвящённых фрескам или мозаикам церкви святых Иоанна и Павла; сборник был создан по указанию папы Симмаха (498–514 гг.). О храме упоминается в указателях римских святынь VII–VIII вв. В Зальцбургском итинерарии (середина VII в.) сообщается о том, что «тела мучеников Иоанна и Павла почивают в большой прекрасной базилике». Согласно итинерарию VII в., сохранившемуся в «Деяниях английских королей» Уильяма из Малмсбери (XII в.), там же находились гробницы святых Криспа, Криспиниана и Бенедикты. Исследователям известно о пожалованиях, сделанных церкви мучеников Иоанна и Павла Римскими папами Константином I, Львом III и Григорием IV, и о восстановительных работах, проведённых по указанию папы Адриана I (772–795 гг.) и карданала Теобальда (конец XI – начало XII вв.). В XIII–XVI вв. неоднократно производились перестройки здания и обновление убранства церкви. В 1573 г., во время ремонта храма, были обретены мощи Иоанна и Павла, которые поместили в главный алтарь. Значительные перестройки церкви, включавшие полную замену внутреннего убранства, переоборудование боковых нефов под капеллы и сооружение монастыря при храме, были произведены в 1668–1689 и 1715–1718 гг. Папа Климент XIV (1769–1774 гг.) передал церковь ордену пассионистов; здесь был похоронен основатель ордена Римско-католической церкви Паоло делла Кроче (Павел Креста). С 1887 г. до середины XX в. под храмом велись археологические исследования. Крупные восстановительные работы, включавшие реставрацию средневековых фасадов и колокольни церкви, были проведены в 1948–1951 гг. на средства кардинала Фрэнсиса Спеллмана.