A Capitania dos Portos da Paraíba foi criada inicialmente pelo Decreto Imperial nº 539, de 3 de outubro de 1847, orientada pelo Decreto nº 358, de 14 de agosto de 1845, que criou as Capitanias dos Portos, mandando instalar a primeira na Corte.
O então Presidente da Província FREDERICO CARNEIRO DE CAMPOS, em 16 de março de 1848, no ato de passagem do Governo da Paraíba do Nordeste, feita pelo Tenente-Coronel de Engenheiros FREDERICO CARNEIRO DE CAMPOS ao Vice-Presidente JOÃO DE ALBUQUERQUE MARANHÃO, referiu-se à criação da Capitania de Portos da Província, nos seguintes termos:

"Acaba de ser criada e instalada nesta província uma Capitania do Porto. Este estabelecimento reputo de vantagem na atualidade, e de muito desenvolvimento e benefícios para o futuro. Ricas matas em madeiras de lei e de construção há nos municípios de Mamanguape e cidade, que por essa Repartição podem ser aproveitadas em prol da Marinha de Guerra."

Em 8 de julho de 1850, pelo Decreto nº 680/1850, a Capitania dos Portos da Província da Parahiba foi extinta. Sendo posteriormente estabelecida pelo Decreto nº 1.944, de 11 de julho de 1857, data em que se comemora o seu aniversário.

O primeiro edifício da Capitania, criado em 1847, situou no local denominado Porto do Capim, na cidade de João Pessoa, nas proximidades da Praça 15 de Novembro, ficando sediada neste local até aproximadamente o ano de 1931, quando foi transferida para a Rua da Areia.

Em 7 de novembro de 1938, o Chefe da Comissão de Inspeção Naval no Brasil, comunicou ao Capitão dos Portos, Capitão de Corveta ALFREDO SALOMÉ DA SILVA, a cessão de um terreno na rua Barão do Triunfo, nº 372, no bairro Varadouro, em João Pessoa, para a construção do edifício da atual Capitania, comunicação esta que anexou o Aviso Ministerial nº 28, de 20 de outubro de 1938, pelo qual o então Ministro da Fazenda atendendo à solicitação do Ministro da Marinha, Vice-Almirante HENRIQUE ARISTIDES GUILHEM, concretizou o referido termo de cessão.

Finalmente, o prédio foi inaugurado no dia 12 de dezembro de 1939, começando a funcionar no dia 19 do mesmo mês e ano, onde a Capitania permanece até os dias de hoje.

Subordinadas à Capitania existiam seis Capatazias, a saber: Baía da Traição, Coqueirinhos, Lucena, Tambaú, Jacumã e Pitimbú, cobrindo todo o litoral da Paraíba, desde o Rio Guajú na fronteira do Estado do Rio Grande do Norte, até o Rio Goiana, no limite do Estado do Pernambuco, atualmente extintas.
Havia, também, subordinada à Capitania, até aproximadamente o ano de 1915, uma escola de Aprendizes-Marinheiros, criada pelo Decreto nº 4.680, de 17 de janeiro de 1871. Até o ano de 1906 o Capitão dos Portos era também Comandante dessa Escola. Inicialmente ela ficou situada no Porto do Capim, em um prédio da Praça Álvaro Machado. Daí foi transferida para o local denominado São Gonçalo, na praia de Tambaú, sendo posteriormente transferida para um edifício situado na Rua Maciel Pinheiro, na cidade de João Pessoa, até que em 1929, aproximadamente, passou a funcionar em um edifício na Avenida João Machado, no bairro de Jaguaribe, quando foi extinta em 1932, sendo este próprio nacional cedido ao Governo Estadual em 1934 a título precário e definitivamente em 14 de março de 1939.

A  denominação  atual  de  “Capitania  dos  Portos  da  Paraíba”  foi  estabelecida  pela  Portaria nº 276 do Ministro de Estado da Marinha, em 19 de setembro de 1997.