Distrito criado com a denominação de Paulista, pela lei municipal nº 219, de 28-12-1907, subordinado ao município de Olinda. Em divisão administrativa referente ao ano de 1911, o distrito de Paulista, figura no município de Olinda.
Elevado à categoria de município com a denominação de Paulista, pela lei estadual nº 1931, de 11-09-1928, desmembrado de Olinda. Sede no antigo o distrito de Paulista. Constituído do distrito sede.
Pelos decretos nº 268, de 25-11-1930 e 56 de 23-01-1931, o município é extinto, sendo seu território voltando a pertencer ao município de Olinda. Em divisão administrativa referente ao ano de 1933, o distrito de Paulista, figura no município de Olinda.
Elevado novamente à categoria de município com a denominação de Paulista, pela lei estadual nº 11, de 04-09-1935, desmembrados de Olinda. Sede no antigo distrito de Paulista. Constituído do distrito sede. Instalado em 12-09-1935.
Em divisões territoriais datadas de 31-XII-1936 e 31-XII-1937, o município é constituído do distrito sede. Pelo decreto-lei estadual nº 235, de 09-12-1938, são criados os distritos de Maricota e Praia da Conceição e anexados ao município de Paulista. No quadro fixado para vigorar no período de 1944-1948, o município é constituído de 3 distritos: Paulista, Maricota e Praia da Conceição. Pela lei municipal nº 39, de 26-11-1948, é criado o distrito de Paratibe ex-Povoado e anexado ao município de Paulista. Pela lei estadual nº 421, de 31-12-1948, o distrito de Maricota passou a denominar-se Abreu e Lima. Em divisão territorial datada de 1-VII-1955, o município é constituído de 4 distritos: Paulista, Abreu e Lima ex-Maricota, Praia da Conceição e Paratibé. Assim permanecendo em divisão territorial datada de 1-VII-1960.
Pela lei estadual nº 4967, de 20-12-1963, desmembra do município de Paulista o distrito de Praia da Conceição. Elevado à categoria de município. Pela lei estadual nº 4993, de 20-12-1963, desmembra do município de Paulista o distrito de Abreu e Lima. Elevado à categoria de município. Em divisão territorial datada de 31-XII-1968, o município é constituído de 2 distritos: Paulista e Paratibe.
Pelo Acórdão do Tribunal de Justiça, mandato de segurança nº 56889, de 27-08-1964, são extintos os municípios de Abreu e Lima e Nossa Senhora da Conceição, voltando a categoria de distritos e pertencendo ao município de Paulista.
Pela lei municipal nº 997, de 26-11-1968, é criado o distrito de Navarro e anexado ao município de Paulista. Em divisão territorial datada de 1-I-1979, o município é constituído de 5 distritos: Paulista, Abreu e Lima, Navarro, Praia da Conceição e Paratibé. Pela lei estadual nº 8950, de 14-05-1982, desmembra do município de Paulista o distrito de Abreu e Lima. Elevado à categoria de município. Em divisão territorial datada de 18-VIII-1988, o município é constituído de 4 distritos:
Paulista, Navarro, Paratibé e Praia da Conceição.
Em divisão territorial datada de 2001. O município é constituído do distrito sede.
Assim permanecendo em divisão territorial datada de 2005.
Fonte: IBGE