It is not known if there were any churches established by Paul in Tarsus, but in 1704, P. Lucas wrote that there was a Romanesque church which had been built by Paul. V. Langlois visited Tarsus in 1851 and confirmed this. In his words, thick walls that resembled the Roman style, windows that are narrower outside than inside, and thick columns are noticeable, but no other records exist to substantiate this claim.
According to tradition the building date of the Saint Paul Church is 1102, but the present structure, a domeless basilica, was built (or rebuilt) much later, in 1862. The entrance to its grounds is via an ornate gateway. The total area of the church building is 460 m2. The longer dimension of the building consists of face stone walls and blind vaults. The interior measures 19.30 m × 17.50 m (63.3 ft × 57.4 ft). In the northeast corner stands an elevated belfry. The sides of the central nave window had been decorated by angels and landscape depictions. On the ceiling there are frescos of Jesus in the middle, and Matthew, Mark, Luke and John at the two sides.
The church has been put under protection since 1993 and a restoration work has been carried on during 1998-2000 period. It is now under the protection of the Ministry of Culture and officially known as Monumental Museum.  Although the church is open to religious services, because of the lack of community, regular services are not held; but ceremonies are held for groups of pilgrims. During Saint Pavlos year between 29 June 2008 and 29 June 2009, there was a number of special ceremonies and the closing ceremony of the year was held in Saint Paul's Church in Tarsus.