Quando o Governador Geral (D. Luís de Brito) recebeu a ordem para separar Itamaracá, recebeu também do rei de Portugal a ordem de punir os índios responsáveis pelo massacre, expulsar o s franceses e fundar uma cidade. Assim começaram as cinco expedições para a conquista da Paraíba. Para isso o rei D. Sebastião mandou primeiramente o Ouvidor Geral D. Fernão da Silva.
- I Expedição (1574): O comandante desta expedição foi o Ouvidor Geral D. Fernão da Silva. Ao chegar no Brasil, Fernão tomou posse das terras em nome do rei sem que houvesse nenhuma resistência, mas isso foi apenas uma armadilha. Sua tropa foi surpreendida por indígenas e teve que recuar para Pernambuco.
- II Expedição (1575): Quem comandou a segunda expedição foi o Governador Geral, D. Luís de Brito. Sua expedição foi prejudicada por ventos desfavoráveis e eles nem chegaram sequer às terras paraibanas. Três anos depois outro Governador Geral (Lourenço Veiga), tenta conquistar a o Rio Paraíba, não obtendo êxito.
- III Expedição (1579): Frutuoso Barbosa impôs a condição de que se ele conquistasse a Paraíba, a governaria por dez anos. Essa ideia só lhe trouxe prejuízos, uma vez que quando estava vindo à Paraíba, caiu sobre sua frota uma forte tormenta e além de ter que recuar até Portugal, ele perdeu sua esposa.
- IV Expedição (1582): Com a mesma proposta imposta por ele na expedição anterior, Frutuoso Barbosa volta decidido a conquistar a Paraíba, mas cai na armadilha dos índios e dos franceses. Barbosa desiste após perder um filho em combate.
- V Expedição (1584): Este teve a presença de Flores Valdez, Felipe de Moura e o insistente Frutuoso Barbosa, que conseguiram finalmente expulsar os franceses e conquistar a Paraíba. Após a conquista, eles construíram os fortes de São Tiago e São Felipe.
Conquista da Paraíba
Para as jornadas o Ouvidor Geral Martim Leitão formou uma tropa constituída por brancos, índios, escravos e até religiosos. Quando aqui chegaram se depararam com índios que sem defesa, fogem e são aprisionados. Ao saber que eram índios Tabajaras, Martim Leitão manda soltá-los, afirmando que sua luta era contra os Potiguaras (rivais dos Tabajaras).
Após o incidente, Leitão procurou formar uma aliança com os Tabajaras, que por temerem outra traição, a rejeitaram.
Depois de um certo tempo Leitão e sua tropa finalmente chegaram aos fortes (São Felipe e São Tiago), ambos em decadência e miséria devido as intrigas entre espanhóis e portugueses. Com isso Martim Leitão nomeou outro português, conhecido como Castrejon, para o cargo de Frutuoso Barbosa. A troca só fez piorar a situação. Ao saber que Castrejon havia abandonado, destruído o Forte e jogado toda a sua artilharia ao mar, Leitão o prendeu e o enviou de volta à Espanha.
Quando ninguém esperava, os portugueses se unem aos Tabajaras, fazendo com que os Potiguaras recuassem. Isto se deu no início de agosto de 1585.
A conquista da Paraíba se deu no final de tudo através da união de um português e um chefe indígena chamado Piragibe, palavra que significa Braço de Peixe.
Fundação da Paraíba
Martim Leitão trouxe pedreiros, carpinteiros, engenheiros e outros para edificar a Cidade de Nossa Senhora das Neves. Com o início das obras, Leitão foi a Baía da Traição expulsar o resto dos franceses que permaneciam na Paraíba.
Leitão nomeou João Tavares para ser o capitão do Forte. Paraíba foi a terceira cidade a ser fundada no Brasil e a última do século XVI.