Paulino nasceu no ano de 355, na cidade de Bordeaux, na França. Seu pai era um alto funcionário imperial e toda a família ocupava posição de destaque na economia e na corte. Antes de se tornar religioso o próprio Paulino foi cônsul e substituiu o governador da Campânia. Nesta posição manteve contato com o bispo Ambrósio de Milão, bem como com o jovem Agostinho, que se tornara Bispo de Hipona, que o encaminharam à conversão. Assim, aos vinte e cinco anos de idade Paulino foi batizado.

Um ano antes tinha se casado com Terásia, uma cristã espanhola que também o influenciou a se aprofundar nos ensinamentos do Evangelho. Quando perderam, ainda criança, o único filho, Celso, os dois resolveram abandonar de vez a vida social e abraçar a vida monástica. De comum acordo, dividiram as grandes riquezas que possuíam com os pobres e as obras de caridade voltadas para o atendimento de doentes e desamparados e se dirigiram para a Catalunha, na Espanha.

Pouco tempo depois, Paulino, que se tornara conhecido e estimado por todo o povo, encaminhou ao Bispo um pedido para que este o ordenasse sacerdote. O que aconteceu, além de ser convidado à participar do clero local ou se preferisse ingressar no de Milão, mas recusou a ambos.