Originally a monk at Rome, in 601 Pope Gregory I sent him to Mellitus and others in the second group of missionaries to England. He was in Kent until 625, when he was consecrated as bishop by Justus and then accompanied Ethelburga, the sister of King Eadbald to Northumbria, where she was to marry King Edwin.
Paulinus eventually convinced Edwin to convert, baptizing him and many of his followers in 627.
When Edwin was defeated and killed in battle in 633, Paulinus took the queen and her children to Kent, and spent the remainder of his life at Rochester.