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 (Forte de São Filipe|São Filipe e Santiago), ambos em decadência e miséria devido as intrigas entre espanhóis e portugueses. Com isso Martim Leitão nomeou o espanhol conhecido como Francisco Castejón para o cargo de Frutuoso Barbosa. A troca só fez piorar a situação. Ao saber que Castejón 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 unem-se 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 Pirajibe, palavra que significa "Braço de Peixe".