A vida deste santo do século VII foi escrita por São Beda o Venerável em sua História Eclesiástica.
Desejando levar uma vida mais perfeita, o futuro Papa São Gregório Magno vendeu suas propriedades na Sicília após a morte do pai em 574, e ali fundou seis mosteiros. Também transformou em mosteiro sua mansão natal no Monte Célio, em Roma, sob a invocação de Santo André, e nele ingressou, sendo eleito abade.
Por volta de 596, cerca de seis anos após ter assumido a Sé de Pedro, circulou em Roma a notícia de que os habitantes pagãos da Grã-Bretanha estavam prontos a abraçar em grande número a fé católica, desde que se encontrassem pregadores capazes de instruí-los.
Realmente, o que de fato ocorria na Inglaterra era que Etelberto, que se tornara rei de Kent, em menos de 20 anos conseguiu estabelecer seu domínio das costas do país dos saxões ocidentais rumo ao Oriente, até o mar; e ao norte, até Humber e Trent. Com isso seu prestígio chegou ao outro lado do Canal da Mancha e levou a Cariberto, rei de Paris, a oferecer-lhe sua filha Berta em casamento. Contudo, no contrato matrimonial, o rei franco estipulou como condição que a filha pudesse exercer livremente a religião católica. Como narra São Beda, a condição foi aceita, pelo que o bispo franco Luidhard acompanhou a princesa na qualidade de capelão.
Foi por essa ocasião que São Gregório enviou à Inglaterra um grupo de monges de seu mosteiro de Monte Célio, chefiados por Agostinho, que mais tarde será conhecido como Agostinho de Cantuária, como missionários.
Para simplificar, Etelberto se converteu à fé católica, levando muitos de seus súditos a seguirem o seu exemplo e, no dia de Natal de 597, milhares deles receberam o batismo.
São Gregório julgou então que era conveniente mandar um segundo grupo de missionários àquele país em 601, para ajudarem Santo Agostinho e os seus. Esse novo grupo era chefiado pelo futuro São Melito, e dele faziam parte, entre outros, São Justo e São Paulino, que chegaram à Inglaterra provavelmente em 604.
Pouco se sabe das atividades de Paulino nas duas décadas seguintes. O que é certo é que ele trabalhou inicialmente em East Anglia e, de 623 a 625 em Kent onde, no dia 21 de julho de 625, recebeu a sagração episcopal como bispo da cidade das mãos de São Justo, que tinha se tornado bispo de Cantuária
Nesse mesmo ano Paulino acompanhou Etelburga, irmã do rei católico Eadbald, de Kent, que ia se casar em Northumbrian Court com o rei Edwin. Os nobres nortúmbrios se mostravam favoráveis à conversão do rei ao cristianismo, e ele alegava que só abraçaria o cristianismo se, após examiná-lo, o julgasse superior à sua religião pagã. O que se deu, levando-o à conversão em 627, sendo ele batizado por São Paulino em York. Desde então o rei demonstrou grande zelo pela conversão de seus súditos.
Entre as damas convertidas por São Paulino na corte de Edwin, estão Hilda, que se tornaria abadessa fundadora da Abadia de Whitby, e sua sucessora Eanfleda, filha do rei.
York se tornou então a base operativa da qual Paulino empreendia sua campanha de pregação junto aos pagãos anglo-saxões. São Gregório havia aconselhado aos missionários a agir com “discrição” junto aos pagãos para atraí-los, não destruindo seus templos mas transformando-os em igrejas, e procurando cristianizar suas festas pagãs.
O santo foi nomeado depois para a Sé de York, que com Cantuária era uma das mais importantes dioceses da Inglaterra. Com a ajuda de Edwin (que também foi canonizado), começou a construir sua catedral com pedra, para se tornar sua catedral.
Seu trabalho apostólico em instruir e batizar o povo foi incessante, e a tradição perpetua seu ministério em Yeavering, Ponte Catterick, Dewsbury, Easingwold, Southwell e outros lugares, sempre acompanhado pela fama de milagres. Seu nome é preservado também na aldeia de Pallingsburn, na Nortúmbria.
Narra São Beda que, por persuasão de Edwin, o rei Eorpwald, de East Anglia, também se converteu ao cristianismo.
Com a morte de São Justo, então arcebispo de Cantuária, São Paulino sagrou outro dos missionários enviados por São Gregório para substituí-lo na Sé vacante.
Ocorreu então que, no dia 12 de outubro de 633, o rei Edwin e seu filho Osfrido foram mortos numa batalha cerca de Doncaster contra o pagão Penda, rei da Mércia, e de seu aliado cristão, o rei gaulês Cadwallon. Durante a refrega, Paulino conseguiu conduzir a salvo a rainha Etelberga e alguns personagens da corte para Kent, deixando seu diácono Tiago, para atender aos católicos na Nortúmbria.
Com a morte de Edwin e a fragmentação do reino, houve um declínio do cristianismo na Nortumbria, tendo os sucessores imediatos do falecido rei voltado ao paganismo.
Nomeado depois bispo de Rochester, Paulino faleceu em 10 de outubro de 644, sendo logo venerado como santo. Para isso contribuiu muito a História Eclesiástica de São Beda, o Venerável, nascido em Nortumbria 28 anos depois de sua morte.
São Beda descreve São Paulino como sendo “um homem de alta estatura, um tanto curvado, com cabelos negros e o rosto magro, um nariz torto e fino, e um aspecto tanto venerável quanto admirável”. Ele provavelmente obteve esta descrição de Tiago, “o Diácono”, companheiro de Paulino, que ainda estava vivo em sua época.
