Na época do descobrimento, os índios que habitavam o litoral paraibano eram os caetés, da família tapuia, atrasados e ferozes. Mais tarde, vieram os potiguares e os tabajaras que expulsaram os tapuias para o interior e construíram suas tabas às margens do rio São Domingos antigamente o rio Paraíba.
Não existem dúvidas de que os primeiros desbravadores da região foram os franceses. Desde o descobrimento do Brasil que os franceses andavam por aqui, carregando o pau - brasil. Data de 1585, a chegada do Ouvidor - Geral da Bahia, Martins Leitão, para desalojar os franceses das posições que ocupavam. Várias batalhas já haviam sido travadas com os franceses que tinham como aliados os índios. O capitão João Tavares, aproveitando-se dos desentendimentos entre as tribos, conseguiu manter contato com os Tabajaras, firmando um pacto de amizade com o murubixaba da tribo, o índio Piragibe. O acordo foi feito no dia 5 de Agosto de 1585, à margem direita do rio Sanhauá, afluente do rio Paraíba.
É exatamente neste local que se encontra hoje a cidade de João Pessoa e como era dia de Nossa Senhora das Neves
o lugar foi batizado com seu nome e a Santa escolhida como padroeira.
Quando Portugal caio no domínio espanhol, João Pessoa teve seu nome modificado para Filipéia em homenagem ao rei da Espanha D. Felipe II.
A 24 de dezembro de 1634, a cidade foi ocupada pelos holandeses, depois de violentos ataques aos fortins da barra, defendidos pelas tropas aquarteladas em Cabedelo. Contava Filipéia com 1500 habitantes e em suas imediações, funcionavam 18 engenhos de açucar. Comandados pelo coronel Segismundo Van Schkoppe 2.500 homens invadiram a cidade que depois da conquista, recebeu o nome de Frederisksdadt, em homenagem ao "Stathouder", holandês.
O povo paraibano não se sujeitou ao jugo estrangeiro e seu espírito de resistência teve como símbolo a figura de André Vital de Negreiros, organizador do movimento de reação. A Paraíba conseguiu libertar-se dos holandeses, em 1654, tomando posse do cargo de governador, João Fernandes Vieira. Data dessa época, a denominação de Paraíba.
Os acontecimentos de 1930 culminaram com o assassinato, em Recife do chefe do governo paraibano, o Presidente João Pessoa. Em sua homenagem póstuma o povo conseguiu a aprovação da Lei estadual nº 700 de setembro de 1930 que mudou o nome do município e da comarca da Paraíba, para João Pessoa.