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 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 Castrejón para o cargo de Frutuoso Barbosa. A troca só fez piorar a situação. Ao saber que Castrejó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".