Paulo de Souza era filho de Francisco das Chagas de Souza e de Alice Paulo de Souza, neto de Manoel Joaquim de Souza (Neco de Sinhá), uma das principais lideranças de Boa Saúde na década de 1930. Nasceu na Fazenda Bom Pasto, no Município de Serrinha, no dia 20/02/1944. Foi casado com a Senhora Ana Maria Fernandes de Souza. Paulo de Souza era engenheiro agrônomo, formado pela Escola Superior de Agronomia de Mossoró.
Primeiro Mandato: 31.01.1977 a 31.01.1983
Nas eleições municipais de 15 de novembro de 1976, foi eleito Prefeito Municipal de Januário Cicco, o Senhor Paulo de Souza e como Vice-Prefeito o Senhor Vivaldo Gomes Brandão, ambos pertencentes à ARENA. O ato de posse foi realizado na sede da Câmara Municipal, no dia 31/01/1977, sob a presidência do Vereador Leonel Gomes da Silva, secretariado pelos Vereadores Fausto José da Costa, 1º secretário e Arnor José da Costa, 2º secretário. Após a transmissão do cargo pela Senhorita Aliete de Medeiros Paiva, o Prefeito Paulo de Souza falou sobre as suas preocupações em relação aos problemas do município, e concluindo, apresentou os seus auxiliares. Em seguida, o Vereador Leonel Gomes da Silva encerrou a solenidade, que contou com a participação de lideranças políticas, autoridades e o povo em geral.
Segundo Mandato: 01.01.1989 a 01.01.1993
Candidatos pela coligação PDS e PFL, nas eleições municipais de l5/11/1988, foram eleitos Prefeito e Vice-Prefeito do Município de Januário Cicco, os Senhores Paulo de Souza e João Félix Neto, que assumiram os respectivos cargos em sessão solene da Câmara Municipal, no dia 01/01/l989, à zero hora, no prédio da Biblioteca Pública Municipal.
A referida sessão foi presidida pelo Vereador Francisco Artur de Souza e secretariada pelos Vereadores José Otacílio do Nascimento e José Maximo Ferreira. Após a posse e a transmissão do cargo ao Prefeito Paulo de Souza pelo Senhor Vivaldo Gomes Brandão, fizeram uso da palavra o Vereador Leonel Gomes da Silva, o Ex Vice-Prefeito Alexandre de Freitas, o Vice-Prefeito recém empossado, Senhor João Félix Neto, o Presidente da Câmara Municipal, Vereador Francisco Artur de Souza e o Prefeito Paulo de Souza, agradecendo aos eleitores a sua eleição, anunciando as primeiras medidas a serem tomadas pela sua administração e nomeando através da Portaria de nº 01/89 o Senhor Heráclito Aguiar para a Chefia de Gabinete.
Terceiro Mandato: 01.01.1997 a 01.01.2001
Nas eleições municipais de 03/10/1996, foram eleitos Prefeito e Vice-Prefeito de Boa Saúde, como candidatos do PFL, os Senhores Paulo de Souza e Mário Cordeiro de Oliveira, que assumiram os respectivos cargos no dia 01/01/l997, às 18 horas, no Clube Social 21 de Abril, em sessão solene da Câmara Municipal de Vereadores, sob a presidência do Vereador Francisco Artur de Souza, tendo como secretários os Vereadores Pedro Francisco dos Santos e Manoel Augusto de Lima.
Após o juramento e cumprida a exigência da legislação federal, em relação à apresentação da declaração de bens, os Senhores Paulo de Souza e Mário Cordeiro de Oliveira foram empossados nos seus respectivos cargos e, em seguida, fizeram uso da palavra o Vereador Auri Lúcio de Souza, os Senhores Aristides Siqueira e Heráclito Aguiar, o Vice-Prefeito Mário Cordeiro de Oliveira e o Prefeito Paulo de Souza, encerrando-se, em seguida, a sessão pelo presidente da mesa.
Quarto Mandato: 01.01.2001 a 01.01.2005
Nas eleições municipais, realizadas no dia 01/10/2000, Paulo de Souza foi reeleito Prefeito do Município de Boa Saúde para mais um mandato de quatro anos.