A ponta do Seixas, ponto mais oriental do território brasileiro, está representada em mapa desde 1502, denominada como monte São Vicente. Dentro do sistema de capitanias hereditárias (1534), couberam a João de Barros e a Aires da Cunha cem léguas de terra entre a foz do rio Jaguaribe a Norte, até à baía da Traição a Sul, compreendo os atuais estados da Paraíba (parte), Rio Grande do Norte e Ceará, como um segundo lote em adição ao do Maranhão. Com o naufrágio da expedição destes donatários, que se dirigiu ao primeiro lote, não foi possível colonizar o senhorio.

Uma revolta dos indígenas potiguar das margens do rio Paraíba, articulada por traficantes franceses de pau-brasil (Caesalpinia echinata), dizimou o Engenho Tracunhaém de Diogo Dias (1574). Para dominar a rebelião, no início do ano seguinte, uma expedição foi enviada da Capitania de Pernambuco, sob o comando do Ouvidor Geral e Provedor da Fazenda Fernão da Silva, sem sucesso. Nova expedição, enviada de Salvador, na Capitania da Bahia pelo governador da Repartição Norte, D. Luís de Brito e Almeida (1573-1578), não conseguiu atingir a Paraíba devido a uma tempestade que lhe dispersou as embarcações, obrigando-as a arribar, avariadas, a Pernambuco, em setembro de 1575. Uma terceira expedição foi armada pelo governo da Capitania de Pernambuco, partindo de Olinda sob o comando de João Tavares (1579), também com êxito limitado.

Finalmente, o governador-geral Manuel Teles Barreto (1583-1587) solicitou o auxílio da frota do Almirante D. Diogo Flores de Valdés, que à época patrulhava a costa brasileira, unindo-se ao Capitão-mor da Paraíba, Frutuoso Barbosa, e organizando nova expedição (1584), que fundou a segunda Cidade Real no Brasil: Filipéia de Nossa Senhora das Neves. O Ouvidor-mor Martim Leitão, com o auxílio das forças do cacique Pirajibe, subjugou os indígenas, erigiu um novo forte e fundou nova e definitivamente a povoação de Filipéia de Nossa Senhora das Neves (4 de novembro de 1585), núcleo da cidade da Parahyba, atual João Pessoa. A paz definitiva com os indígenas, entretanto, só foi alcançada em 1599, após uma epidemia de bexigas (varíola) que dizimou a população nativa.

No contexto da segunda das Invasões holandesas do Brasil (1630-1654), a região foi ocupada por forças neerlandesas (1634), que somente foram expulsas duas décadas mais tarde pelas tropas do Mestre-de-Campo André Vidal de Negreiros (1606-1680) e de João Fernandes Vieira, que tomou posse do cargo de Governador da cidade, que passou a chamar-se Parahyba.

Mapa da Capitania da Paraíba, 1698.A partir de 1753 a Capitania da Paraíba ficou subordinada à Capitania Geral de Pernambuco, da qual se tornou novamente independente a partir de 1799.

No século XIX, sofreu os reflexos da Revolução Pernambucana (1817), e da Confederação do Equador (1825).

No ano de 1930, a chamada Guerra de Princesa envolveu as oligarquias locais, registrando-se o assassinato do governador do Estado, João Pessoa Cavalcanti de Albuquerque (Recife, 26 de julho de 1930), indicado como vice-presidente na chapa de Getúlio Vargas, candidato (derrotada) à presidência da República. O fato foi manipulado como um dos estopins da Revolução de 1930. Comovida com o evento, a capital paraibana passou a ser denominada "João Pessoa".

O Hino Oficial do Estado da Paraíba, possui a poesia de Francisco Aurélio Figueiredo e Melo e a música de Abdon Felinto Milanez:

            Salve, berço do heroísmo,
            Paraíba, terra amada,
            Via-láctea do civismo
            Sob o Céu do Amor traçada!

            No famoso diadema
            Que a Pátria a fronte aclara
            Pode haver mais ampla gema:
            Não há-Pérola-mais rara!
   
            Quando repelindo o assalto
            Do estrangeiro, combatias,
            Teu valor brilhou tão alto
            Que uma Estrela-parecias!

            Tens um passado de glória,
            Tens um presente sem jaça:
            Do Porvir canta a vitória
            E, ao teu gesto - a Luz se faça!

            Salve, ó berço do heroísmo,
            Paraíba, terra amada,
            Via-láctea do civismo
            Sob o Céu do Amor traçada!

 A bandeira da Paraíba traz consigo o símbolo Nego que representa o protesto de João Pessoa, quando não aceitou a candidatura de Júlio Prestes à Presidência da República como sucessor de Washington Luís, em letras brancas sobre o fundo rubro-negro onde o vermelho ocupa dois terços do espaço e o preto apenas um terço, ao lado do mastro. A cor vermelha representa o sangue derramada por João Pessoa (ele foi assassinado) e a cor negra representa o estado de luto em que a Paraíba se encontrava no momento, em função de seu assassinato, a capital do Estado passou a chamar-se João Pessoa.

O Escudo do Estado da Paraíba possui três ângulos na parte superior e um na parte inferior, contendo 15 estrelas azuis que representam a divisão administrativa em Comarcas. No alto, há uma estrela maior com um barrete frígio (boné de feltro com o qual o senhor cobria a cabeça do escravo na cerimônia de liberdade), significando liberdade. No interior do escudo, há duas paisagens: uma representando um trecho do litoral com o sol nascente, e outra, um campo de criação com um pastor, numa alusão ao Sertão. Circundado-o, encontra-se uma ramagem de cana-de-açúcar à esquerda, e à direita, uma de algodão que se entrelaçam. No ponto da fusão, há uma laço vermelho, numa faixa, onde lê-se "5 de agosto de 1585", a data oficial da fundação da Paraíba.