Hıristiyanlığın MS IV. yüzyılda Bizans İmparatoru Constantinius tarafından resmen tanınmasından sonra dini baskılar kalkmış, Hıristiyan kiliseleri yaygınlaşmaya başlamıştır. MS V. yüzyıldan itibaren de, Kıbrıs, Anadolu, Yunanistan ve Ege adalarına misyonerlik yolculukları yaparak İsa Mesih, Müjde, vaftiz, Hristiyanlığın kurtuluşu ve yayılması gibi öğretilerde bulunan Aziz Paul adına çok sayıda kilise inşa edilmiştir. Bu kiliselerden bazıları da Aziz Paul’un doğum yeri olan Tarsus’ta yer almaktadır. Ancak günümüze bu kiliselerden sadece bir tanesi ulaşabilmiştir. İnanışa göre günümüze ulaşan Aziz Paul Kilisesi’nin yapım tarihi 1102’dir. Ancak kubbesiz bir bazilika olan yapı 1862 yılında geçirdiği büyük çaplı onarımdan sonra genel mimari olarak bugünkü halini almıştır.

Ulu Camii semtinde yer alan kilise, Hıristiyan ahalinin Tarsus’tan ayrılmasından sonra terk edildi, binada bazı değişikler yapılarak 1993 yılına kadar çeşitli amaçlarla kullanıldı. 1994 yılında Kültür Bakanlığı’na tahsis edilerek koruma altına alındı, St. Paul Anıt Müzesi olarak adlandırıldı. 1997-2001 yıllarında mimari koruma, onarım ve içte yer alan duvar resimleri üzerinde büyük çaplı restorasyon çalışmaları sürdürüldü. Restorasyon çalışmaları 2001 yılında tamamlan Kilise, Anıt Müze olarak ziyarete açıldı.

St. Paul Anıt Müzesi'nin, ön giriş kapısı kuzey tarafta ve anıtsal niteliktedir. Girişin hemen sağında, bahçe içerisinde Kilisenin su kuyusu yer almaktadır. Yapının toplam alanı 460 metrekare olup, dikdörtgen biçim oluşturan planı oldukça basittir. Daha uzun tarafı kesme taş duvarlar ve kör tonozlardan oluşmaktadır. Batıda dört sütunun taşıdığı tonozlu bir sundurma yer almakta olup, bu tonozların iç kısmı gök mavisine boyanmış, köşeler stilize bitki motifler ile süslenmiştir. Ana giriş kapısı kemerlidir, yanlarda birer pencere bulunmaktadır. İç mekan 19,3x17,5 metre boyutlarındadır. Kilisenin sütun başlıkları korinth tarzı esas alınarak boyanmıştır. Kilisenin zemin beyaz ve siyah mermerle kaplıdır.

Üç nefli kilisenin, orta nefinin tavanında Hz. İsa, İncil yazarları Yohannes, Mattios, Marcos ve Lucas ile bir göz motifi ve bir kuş figürünün olduğu freskler yer almaktadır. Havariler İncil yazarken, Hz. İsa ise sağ eli önde resmedilmiştir. Orta nef ile apsisin kesiştiği kısımdaki kutsal mekân, süslemeli mermer bir paravanla ayrılmıştır. Apsisin üst kısmında yer alan pencerenin iki yanında ise manzara ve melek tasvirleri yer almaktadır. İç duvarlardaki nişler, ikona ve Aziz tasvirleri için yapılmıştır. Bu nişlerin benzerleri yanlardaki küçük apsislerde de bulunmaktadır.

St. Paul Anıt Müzesi, Hristiyanlar için önemli bir hac yeridir. Dini törenlere açık olmasına rağmen, cemaat eksikliği nedeniyle düzenli ayinler yapılmamakta, ancak ziyarete gelen yerli ve yabancı gruplar için dini törenler de gerçekleştirilmektedir. 1992-93 yıllarında Vatikan’ın düzenlediği Aziz Paul Sempozyumu ve Töreni'ne ev sahipliği yaptı. Papa 16. Benediktus’un Aziz Paul’ün doğumunun iki bininci yıl dönümü dolayısıyla 28. 06. 2008 ve 29. 06. 2009 arasını St. Paul Yılı ilan etmesiyle bilinilirliği daha da arttı. St. Paul yılında bir dizi özel tören düzenlendi ve yılın kapanış ayini burada yapıldı. Kilise/ Anıt Müze ve çevresi 25.02.2000 tarihinde Birleşmiş Milletler Dünya Mirası Geçici Listesi’ne alındı. Günümüzde, Kültür ve Turizm Bakanlığı’na bağlı St. Paul Anıt Müzesi olarak hizmet vermektedir.