Segundo tradições locais, os índios tabajaras foram os primeiros povoadores das terras do atual município de Paudalho, que começaram a ser exploradas em fins do século XVI, com o corte do pau-brasil em suas florestas. A ocupação regular dessa região teria sido iniciada por volta de 1591, nos extremos de Goiana, Igarassu e Tracunhaém, a cerca de duas léguas da margem esquerda do rio Capibaribe, quando os franciscanos fundaram um aldeamento de índios. Esse aldeamento ficava em terras do distrito de Santo Antônio de Tracunhaém, que depois passou à freguesia de Igarassu. Era a aldeia do conhecido índio Poti (D. Felipe Camarão), que tanto se celebrizou na guerra contra os holandeses. Esse local tem ainda hoje o nome de Miritiba, corruptela do tupi mbiri-tyba que, segundo alguns autores, significa “juncal”.

Aos primitivos habitantes juntaram-se os colonizadores, e o povoado ingressou em uma fase de desenvolvimento, com atividades agrícolas e de pastoreio. Em consequência do plantio da cana-de-açúcar começaram a surgir vários engenhos. O primeiro que a história registra foi o Mussurepe, instalado por volta de 1630, na margem esquerda do Capibaribe, a 6 km da atual cidade de Paudalho, onde depois se instalou uma usina com o mesmo nome.

No ano de 1660, nas terras de Miritiba, foi construído o Engenho Aldeia por Bartolomeu de Holanda Cavalcanti. No mesmo local do povoado indígena original existe hoje um quartel, com campo de instrução militar. Ainda na segunda metade do século XVII surgiu o Engenho Bom Sucesso, fundado por Joaquim de Almeida. Em 8 de janeiro de 1711 chegara à margem esquerda do Capibaribe o português Joaquim Domingos Telles, residente em Itamaracá, onde cultivava terras, trazendo alguns parentes e muitos escravos africanos. Vinha explorar novos terrenos, apropriados para a cana-de-açúcar.

No local ele fundou o Engenho Paudalho, o mais importante da região, que daria origem e batizaria o povoado. A denominação decorre da existência em suas terras, à margem direita do rio Capibaribe, de alguns exemplares de pau-d’alho, também conhecido como guararema (do tupi gwra’rema, que significa madeira malcheirosa). Essa árvore (Gallesia sp.), da família das fitolacáceas, é nativa do Brasil e do Peru, podendo atingir até 40 m de altura. A sua madeira verde exala forte odor de alho, daí a denominação. Ainda hoje existe, no mesmo local, uma árvore proveniente de um exemplar original, conservada pela prefeitura. Pelo uso, “paud’alho” sofreu aglutinação, passando a Paudalho.

Devido à distância que ficava do curato de Nossa Senhora do Desterro (hoje Itambé), os moradores do novo engenho, reunidos ao proprietário, construíram uma capela, sob a invocação de Santa Tereza de Jesus, por se chamar Tereza a esposa de Joaquim Domingos Telles. A nova capela foi inaugurada em 13 de outubro de 1711, havendo nessa ocasião grandes festas. A primeira missa foi celebrada pelo padre Júlio da Cunha, residente na cidade de Olinda. Baseado na nascente economia canavieira o núcleo populacional existente consolidouse em torno do Engenho Paudalho e essa atividade econômica disseminou-se por toda a região.

O distrito de Paudalho foi criado em 1789. Em 1799, tendo a povoação atingido certo grau de importância, o bispo D. José Joaquim da Cunha Azeredo Coutinho nela estabeleceu um curato, desmembrando-a de Igarassu. As instruções foram dadas pelo bispo, em 31 de agosto desse mesmo ano, ao cônego visitador do bispado, D. Joaquim Saldanha Marinho. Essas instruções acham-se registradas na Câmara Eclesiástica, no Arcebispado de Olinda e Recife. A capela do Espírito Santo foi ereta em matriz, e a provisão de cura, com toda jurisdição necessária, recaiu no padre José Fernandes de Moura Pacheco, que ali residia na qualidade de coadjutor. Em 22 de junho de 1804 o curato foi elevado à categoria de freguesia, por alvará, o mesmo que confirmou a criação do distrito de Paudalho.

Em decorrência da representação do governador da província, Caetano Pinto de Miranda Montenegro, de 06 de dezembro de 1809, foi criada a vila de Paudalho (Páo de Alho, na grafia da época), por alvará régio de 19 de agosto de 1811, com território desmembrado dos termos da cidade de Olinda e do antigo município de Igarassu. A vila só foi instalada em 16 de maio de 1812, pelo ouvidor Clemente Ferreira França. Ao termo da vila de Paudalho foram vinculados os distritos das freguesias de Paudalho e da Luz e parte da freguesia de São Lourenço.

A comarca de Paudalho foi criada pela Lei Provincial nº 86 (art. 3º), de 08 de maio de 1840, desmembrada da comarca de Olinda, sendo instalada no mesmo ano pelo juiz Antônio Batista Gitirana. Essa lei que criou a comarca aparece com datas divergentes em algumas publicações: 08 de maio de 1840 (no Calendário Oficial de Datas Históricas dos Municípios de Pernambuco); 05 de maio de 1840 (Sebastião de Vasconcelos Galvão); e 06 de maio de 1870 (na Enciclopédia dos Municípios Brasileiros, do IBGE, e também na publicação “História das Comarcas Pernambucanas”, do Tribunal de Justiça de Pernambuco).

A vila de Paudalho foi elevada à categoria de cidade, com a denominação de cidade do Espírito Santo, pela Lei Provincial nº 1.318, de 04 de fevereiro de 1879. Mas essa denominação determinada pela lei não foi seguida pela população, que continuou adotando a denominação de Paudalho, a que estavam acostumados. Nesse mesmo ano de 1879 foi iniciada pela Great Western of Brazil Railway a construção da estação ferroviária, inaugurada dois anos depois, no dia 26 de outubro de 1881.

A Lei Municipal nº 1, de 05 de dezembro de 1892, confirmou o distrito de Paudalho. O município foi constituído no dia 3 de abril de 1893, adquirindo autonomia legislativa, com base na Constituição Estadual e no artigo 2º das disposições gerais da Lei Estadual nº 52 (Lei Orgânica dos Municípios), de 3 de agosto de 1892, promulgada durante o governo de Alexandre José Barbosa Lima. O primeiro prefeito eleito foi o tenente-coronel José Francisco Pinheiro Ramos. A Lei Municipal nº 12, de 15 de dezembro de 1901, criou o distrito de Floresta dos Leões, o qual foi posteriormente elevado à categoria de vila , ainda subordinado a Paudalho , pela Lei Estadual nº 991 , de 1º de julho de 1909. Em divisão administrativa referente ao ano de 1911, o município é constituído de dois distritos: Paudalho e Floresta dos Leões.

A Lei Estadual nº 1.931, de 11 de setembro de 1928, desmembrou de Paudalho o distrito de Floresta dos Leões, o qual foi elevado à categoria de município, com a mesma denominação (atual município de Carpina). Em divisão administrativa referente ao ano de 1933 Paudalho é formado apenas pelo distrito sede, assim permanecendo em divisões datadas de 31 de dezembro de 1936 e 31 de dezembro de 1937.

A comarca de Paudalho foi extinta pelo Decreto-lei Estadual nº 952, de 31 de dezembro de 1943, passando a termo judiciário da comarca de São Lourenço da Mata. Mas foi restaurada, como comarca de 2ª entrância, pelo Decreto-lei Estadual nº 1.116, de 14 de fevereiro de 1945, tendo como juiz instalador Severino Correia de Araújo.

Pela Lei Municipal nº 17, de 08 de março de 1948, foi criado e anexado a Paudalho o distrito de Lagoa de Itaenga, cuja criação foi confirmada ainda pela Lei Estadual nº 421, de 31 de dezembro desse mesmo ano. Em divisão territorial datada de 1º de julho de 1955 o município aparece com dois distritos: Paudalho e Lagoa de Itaenga, assim permanecendo em divisão territorial datada de 1º de julho de 1960. A Lei Estadual nº 4.966, de 20 de dezembro de 1963, desmembrou o distrito de Lagoa de Itaenga, elevando-o à categoria de município. Em divisão territorial datada de 18 de agosto de 1988 o município é constituído apenas pelo distrito sede, assim permanecendo em divisão de 2005.