Den hellige Paulus (sp: Pablo) ble født på 800-tallet i Córdoba i Sør-Spania, som på den tiden var maurernes hovedstad. Maurerne var afrikanske muslimer som hadde erobret Spania på 700-tallet. Midt på 800-tallet drev de kristenforfølgelser under emir Abderrahman (Abd al-Rahman) II (822-52).
Paulus hadde vært elev på skolen ved kirken St. Zoilo i Córdoba. Han var en både nestekjærlig og sjarmerende ung mann og ble diakon ved St. Zoilo, og var svært nidkjær i sin tjeneste for de kristne som var fengslet av muslimene. Paulus beskyldte offentlig muslimene for tom kunnskap og deres profet for galskap, og bekjente at Kristus var den sanne Gud. Han ble da fengslet og kastet i et fangehull, hvor han fant en prest ved navn Tiberino, som hadde sittet der i 20 år. Paulus ble henrettet den 20. juli, og få dager senere fikk Tiberino reise tilbake til sin hjemby.
Paulus' lik ble liggende utenfor palassets murer uten å bli gravlagt, men ble senere berget av hans medkristne sammen med liket av munken Theodemir, som led martyrdøden den 25. juli. Begge ble gravlagt i koret i kirken St. Zoilo.
Paulus' minnedag er dødsdagen 20. juli. Han kalles også Paulus av St. Zoilus. Beretningen om hans martyrium ble skrevet av den hellige presten Eulogius av Córdoba, som førte en protokoll over dem som led martyrdøden mellom 822 og 859 og beskrev deres lidelse og død i forfølgelsene. Dette var verket Memorialis Sanctorum, «De helliges minne». For bakgrunn samt oversikt over alle martyrene mellom 822 og 859, se Martyrene av Córdoba.