História
Frei Paulo é obra de um missionário italiano e de uma pedra fincada num planalto vazio. Em meados da década de 1860, o bispo e religiosos de Itabaiana convidaram o capuchinho Frei Paulo de Casa Nova — genovês, nascido em 1º de dezembro de 1813 e falecido em Salvador em 30 de janeiro de 1891 — para celebrar missas na região; ele trouxe consigo Frei Davi de Umbértide. Depois de uma missa na localidade da Chã de Jenipapo, Casa Nova encontrou um amplo planalto desabitado e articulou com as autoridades locais a abertura de uma missão. Com o apoio dos capitães José Alves Teixeira e Antônio Telles de Góes, fincou a primeira pedra da Igreja de São Paulo em 25 de janeiro de 1868. Ao redor dela cresceu o arraial, com a ajuda de Antônio Teixeira, Lourenço da Rocha Travassos e Tomaz de Aquino e Silva, e, ao chegar a cem residências, virou distrito de Itabaiana em 1886, com o nome de São Paulo. A emancipação como vila veio pelo Decreto-lei estadual nº 11, de 25 de janeiro de 1890 — no vigésimo segundo aniversário da fundação, e instalada no mesmo dia —, e a condição de cidade pela Lei estadual nº 795, de 23 de outubro de 1920. A troca de nome tem duas versões oficiais: a Prefeitura data a mudança para Frei Paulo em 2 de março de 1938, com o distrito-sede rebatizado em dezembro de 1943; o IBGE registra o Decreto-lei estadual nº 377, de 31 de dezembro de 1943, revogado pelo Decreto nº 533. Entre a República Velha e o Estado Novo o município teve dezoito interventores; Napoleão Emygdio da Costa foi o primeiro prefeito indicado, em 1938, e Izauro Soares, o primeiro eleito, em 1947.