Paulinus was baptised shortly before his departure to Spain, that is ca 389. He was ordained presbyter in Barcelona at Christmas 394. In the letter in which he gives details of his ordination, he stresses that he was not ascribed to the Church of Barcelona nor to any other city . At the time of writing of the letter presented in this record, he was almost certainly already in Nola (Italy) where he established a monastery in 395.
Paulinus is very careful to always address bishops as fathers and fellow presbyters as brothers (for example Augustine of Hippo, who was at that time still a presbyter, see also ).