João Tavares

João Tavares foi o primeiro capitão-mor, ao qual governou de 1585 a 1588 a Capitania da Paraíba.

João Tavares foi encarregado pelo Ouvidor-Geral, Martim Leitão, de construir uma nova cidade. Para edificação dessa cidade, vieram 25 cavaleiros, além de pedreiros e carpinteiros, entre outros trabalhadores do gênero. Chegaram também jesuítas e outras pessoas para residir na cidade.
Foi fundado por João Tavares o primeiro engenho, o d'El-Rei, em Tibiri, e o forte de São Sebastião, construído por Martim Leitão para a proteção do engenho.

Os jesuítas ficaram responsáveis pela catequização dos índios. Eles ainda fundaram um Centro de Catequese e em Passeio Geral edificaram a capela de São Gonçalo.

O governo de João Tavares foi demasiadamente auxiliado por Duarte Gomes da Silveira, natural de Olinda.
Silveira foi um senhor de engenho e uma grande figura da Capitania da Paraíba durante mais de 50 anos. Rico, ajudou financeiramente na ascensão da cidade. Em sua residência atualmente se encontra o Colégio Nossa Senhora das Neves.

Apesar de ter se esforçado muito para o progresso da capitania, João Tavares foi posto para fora em 1588, devido à política do Rei.

Frutuoso Barbosa

Devido à grande insistência perante a corte e por defender alguns direitos, Frutuoso Barbosa foi, em 1588, nomeado o novo capitão-mor da Capitania da Paraíba, auxiliado por D. Pedro Cueva, ao qual foi encarregado de controlar a parte militar da capitania.

Neste mesmo período, chegaram alguns Frades Fransciscanos, que fundaram várias aldeias e por não serem tão rigorosos no ensino religioso como os Jesuítas, entraram em desentendimento com estes últimos. Esse desentendimento prejudicou o governo de Barbosa, pois aproveitando-se de alguns descuidos, os índios Potiguaras invadiram propriedades. Vieram em auxílio de Barbosa o capitão-mor de Itamaracá, com João Tavares, Piragibe e seus índios. No caminho, João Tavares faleceu de um mal súbito. Quando o restante do grupo chegou à Paraíba, desalojou e prendeu os Potiguaras.

Com o objetivo de evitar a entrada dos franceses, Barbosa ordenou a construção de uma fortaleza em Cabedelo.

Piragibe iniciou a construção do forte com os Tabajaras, porém, devido a interferência dos Jesuítas, as obras foram concluídas pelos franciscanos e seus homens.

Em homenagem a Felipe II, da Espanha, Barbosa mudou o nome da cidade de Nossa Senhora das Neves para Felipéia de Nossa Senhora das Neves.
Devido às infinitas lutas entre o capitão Pedro Cueva e os Potiguaras e os desentendimentos com os Jesuítas, houve a saída da Cueva e a decisão de Barbosa de encerrar o seu governo, em 1591.

André de Albuquerque Maranhão

André de Albuquerque governou apenas por um ano. Nele, expulsou os Potiguaras e realizou algumas fortificações. Entre elas, a construção do Forte de Inhobin para defender alguns engenhos próximos a este rio.
Ainda nesse governo os Potiguaras incendiaram o Forte de Cabedelo. O governo de Albuquerque se finalizou em 1592.

Feliciano Coelho de Carvalho

Em seu governo realizou combates na Capaoba, houve paz com os índios, expandiu estradas e expulsou os fransciscanos. Terminou seu governo em 1600.