Criada de direito em 1574, a Paraíba somente começou a existir de fato em 1585 com a fundação da cidade de Filipéia de Nossa Senhora das Neves. O retardamento da conquista explica-se:
Pelas lutas travadas na insurreição contra os holandeses.
Pela resistência dos índios da confederação dos Cariris.
Pela aliança celebrada por Martim Leitão e os índios Tabajaras do cacique Piragibe.
Pela resistência dos índios Potiguaras aliados aos franceses, traficantes de pau-brasil.