Terras descobertas por volta de 1868 por missionários capuchinhos, entre eles frades Davi de Umbértide e Paulo Antônio Casanova. Este último deu o nome ao município.
Mas essa história começa muito antes. Quando os capuchinhos chegaram encontraram os índios comandados por Imbiracema. O lugar era conhecido como as ‘matas de Itabaiana', uma região propícia para o cultivo do algodão e a criação de gado. Além de índios, muitos ‘brancos' da crescente Vila de Itabaiana iam para lá. Por causa dos jenipapais, o lugar era conhecido como Chã de Jenipapo.
Em Itabaiana, os frades Paulo Casanova e Davi de Umbértide foram convidados por José Alves Teixeira e Brás Vieira de Matos, proprietários de terras em Chã de Jenipapo, para conhecer o lugar. Foram e ficaram. Providenciaram madeira e ergueram a capela de São Paulo. Naquela data comemorava-se o dia do apóstolo Paulo de Damasco. Também colaboraram para a formação do povoado, Antônio Teixeira, Lourenço da Rocha Travassos e Tomaz de Aquino e Silva.
Nossa São Paulo
O povoamento de Chã de Jenipapo passava a ser conhecido como aldeia de São Paulo. Em 29 de abril de 1886, o presidente da Província de Sergipe, Manoel de Araújo Góes, transforma a povoação em freguesia de São Paulo. O capitão João Tavares da Mota foi um dos maiores responsáveis pelas edificações do povoado. Nesse período, também fixa residência na região um judeu francês Goottchaux Ettinger, que montou a mais importante indústria descaroçadora de algodão.
Em 1890, com a chegada da República, o governador do Estado, Felisbelo Freire, atendendo a pedido do capitão Antônio Cornélio da Fonseca, transforma a freguesia em Vila de São Paulo de Itabaiana. Em 23 de outubro de 1920, por forte influência de um dos filhos mais ilustres de São Paulo, o engenheiro Gentil Tavares da Mota, a vila muda para cidade. Em 2 de março de 1938, por causa da repetição de nomes, São Paulo do sertão sergipano ganha o nome de Frei Paulo, homenagem ao seu fundador. Por algum tempo, os que nasciam lá eram chamados de paulistanos. Depois da mudança de nome para Frei Paulo, surgem os apelidos de ‘São Paulo moleque' e ‘São Paulo calça curta', mas oficialmente os nativos passam a se chamar frei-paulistanos.
