Den hellige Paulinus ble født ca 575, trolig i Italia. Han tilhørte den andre gruppen av munker som pave Gregor den Store sendte til England i 601 for å assistere den første gruppen under erkebiskop Augustin. Den hellige Beda den Ærverdige beskriver ham som «en høy, mørk mann, svakt lutende, med et tynt ansikt og en smal ørnenese, med en ærverdig og ærefryktinngytende skikkelse».
Da den hellige kong Edwin av Northumbria ville gifte seg med prinsesse den hellige Ethelburga, den kristne søsteren av kong Edbald av Kent, fikk han ja under forutsetning av at hun fritt kunne utøve sin religion. Edwin lovte også å vurdere å bli en kristen. Paulinus ble viet til den første biskop av York i Northumbria av den hellige erkebiskop Justus i Canterbury og dro i 625 nordover som dronningens kapellan med et håp om å omvende konge og folk.
Påsken 627 ble kong Edwin og hans nyfødte datter Enfleda døpt i en trekirke i York. Avgjørende for kongen var blant annet at den hedenske ypperstepresten Coifi besluttet å avsverge sin gamle tro, og ble fulgt av mange adelsmenn og andre. Paulinus døpte dem i elvene Swale ved Catterick og Glen ved Yeavering samt andre steder i Yorkshire og Lincolnshire, og sammen med diakonen St. Jakob døpte han mange i elva Trent ved Littleborough. Den hellige Beda den Ærverdige skildrer hendelsene i detalj En mye mindre foretrukket kilde, den walisiske Nennius, tilskriver dåpen en walisisk prest, en viss Rum map Urgen, men både Beda og Gregor den Stores første biograf, som støtter ham, er mye eldre og mer uavhengige og troverdige kilder.
Paulinus fulgte opp med en serie av misjonsreiser over et stort område, og dro så langt sør som til Lincoln, mens han omvendte og døpte store mengder. Han bygde en steinkirke i Lincoln, hvor han i 628 viet den hellige Honorius til erkebiskop av Canterbury. Pave Honorius I (625-38) knyttet i 634 engelskmennene nærmere til Roma ved å gi pallier til erkebiskopene Honorius av Canterbury og Paulinus av York med instruksjoner om at når en av dem døde, skulle den andre utpeke hans etterfølger. Men før brevet med denne anerkjennelsen av Paulinus som erkebiskop av York kom frem, var den første evangeliseringen av Northumbria over og Paulinus allerede tilbake i Kent. Under de siste årene av kong Edwins regjering var det slik ro og orden i hans riker at et munnhell sa at «en kvinne kunne bære sitt nyfødte barn tvers over øya fra hav til hav uten å lide noen overlast» (St. Beda).
Paulinus' nordlige apostolat ble avbrutt da kong Edwin ble beseiret av den hedenske kong Penda av Mercia og hans kristne allierte Cadwallon fra Wales og drept i slaget ved Hatfield Chase den 12. oktober 633. Paulinus, som ikke hadde tro på noen fremtid for kristendommen i Northumbria uten kongen, tok med seg dronning Ethelburga og hennes barn og flyktet med dem sjøveien tilbake til Kent.
Paulinus hadde etterlatt sin diakon Jakob for å fortsette arbeidet i nord som best han kunne, og selv virket han som biskop av Rochester resten av livet. Han døde i Rochester den 10. oktober 644, omkring 70 år gammel.
Han ble feiret 10. oktober, spesielt i klostre og i Nord-England. Det var også en kult for ham i Canterbury og Rochester. Datoene for hans apostolat er omstridt, de siste antakelsene er at det begynte så tidlig som 619 i stedet for det tradisjonelle 625. Hans navn står i Martyrologium Romanum.