The building is believed to be located over a previous edifice housing the remains of the Córdoban martyrs Januarius, Martial and Faustus, dating to the 4th century AD. After the conquest of the city by king Ferdinand III of Castile (1236), a church dedicated to St. Paul was built here in his program of construction to give a Christian appeal to the previously Muslim city. Construction began in the late 13th century and was completed in the early 14th century.
The edifice's current appearance date mostly to later restorations. Part of the bell tower and two of the medieval gates have survived, a new one having been added by architect Hernán Ruiz II in 1542. In 2006, the church was elevated to the status of minor basilica by Pope Benedict XVI. It is a Bien de Interés Cultural monument.
- San Pedro at Cordobapedia (in Spanish)