O município de Paulista se situa na área da antiga propriedade Paratibe (nome também do rio que banha parte da cidade). As terras de Paratibe foram doadas pelo donatário da Capitania de Pernambuco, Duarte Coelho Pereira, a seu cunhado, Jerônimo de Albuquerque, como reconhecimento por serviços prestados à Capitania. Alguns anos após, pela década de 1550, Jerônimo de Albuquerque fez doação dessas terras, em dote, ao português Gonçalo Mendes Leitão, esposo de Dona Antônia de Albuquerque, sua filha com a índia tabajara Muíra-Ubi, que adotara o nome cristão Maria do Espírito Santo Arcoverde.
Nessas terras, Gonçalo Mendes Leitão ergueu um engenho-d’água, uma capela dedicada a Santo Antônio e um grande sobrado como residência, também outras obras importantes para um estabelecimento agrícola. Erguida a capela, no ano de 1559, coincidiu de passar por Pernambuco, a caminho da Bahia, o bispo eleito do Brasil, D. Pedro Leitão, irmão de Gonçalo Mendes. Hospedado na casa de seu irmão, em Paratibe, o bispo celebrou o ato solene da bênção da capela, cerimônia à qual compareceu Jerônimo de Albuquerque.
No final do século XVI, um dos filhos de Gonçalo Mendes Leitão fundou o Engenho Paratibe de Baixo que posteriormente passou a ser propriedade de João Fernandes Vieira, em seguida da sua viúva, Dona Maria César, que o vendeu ao mestre-de-campo Manuel Alves de Morais Navarro. Data dessa época (1689) a mudança do nome do engenho que passou a ser conhecido como “Engenho do Paulista”, tendo em vista o novo proprietário ser natural da Capitania de São Paulo, de onde partira no comando de tropas para a Campanha dos Palmares. O nome desse engenho deu origem ao topônimo municipal.
Um fato marcante na história de Paulista ocorreu em 20 de maio de 1817, quando o padre João Ribeiro Pessoa de Melo Montenegro, integrante da Revolução Pernambucana, suicidou-se ao ver a causa perdida. Seu cadáver, sepultado na capela do Engenho Paulista, foi desenterrado e mutilado; a cabeça, separada do tronco, foi levada para a capital do estado e colocada no pelourinho por ordem do almirante Rodrigo Lobo, comandante da esquadra enviada da Bahia pelo conde dos Arcos, para reprimir o levante.
O boom do crescimento populacional de Paulista só começou a surgir com o início das operações da fábrica de tecidos, adquirida em 1904 pela família Lundgren, de imigrantes suecos. O distrito de Paulista foi criado pela Lei Municipal n° 219, de 28 de dezembro de 1907, subordinado ao município de Olinda. A Lei Estadual n° 1.931, de 11 de setembro de 1928, criou o município de Paulista, constituído por territórios desmembrados de Olinda (distritos de Paulista, Canoas, Nobre e Conceição), Igarassu (parte do distrito de Maricota, além dos engenhos Improviso e Regalado e propriedade Pitanga do Inglez) e São Lourenço da Mata (Engenho Utinga). Mas o município foi extinto pelos decretos n° 268, de 25 de novembro de 1930, e n° 56, de 23 de janeiro de 1931, sendo seu território reanexado ao município de Olinda. Foi elevado novamente à categoria de município, com a denominação de Paulista, pela Lei Estadual n° 11, de 4 de setembro de 1935, desmembrado de Olinda, com sede no antigo distrito de Paulista. Foi instalado no dia 12 do mesmo mês e ano.
Durante as primeiras sete décadas do século XX Paulista foi uma cidade típica industrial, até a decadência do parque têxtil tradicional. A partir dos anos 70, entretanto, um pólo industrial moderno, instalado no distrito industrial de Paratibe, deu outra feição ao município.