Antes de la llegada de los europeos, el litoral de la actual Paraíba estaba habitado por los potiguaras —cuyo nombre significa 'comedores de camarón' en tupí—, que dominaban las márgenes del río Paraíba, y por los tabajaras, además de pueblos del interior como los cariris y los ariús. Los potiguaras tejieron una alianza estratégica con los mercaderes franceses que traficaban palo brasil en la costa, lo que los convirtió en enemigos temibles de la corona portuguesa durante casi todo el siglo XVI.
La conquista de la Paraíba fue una de las más largas y difíciles de todo Brasil: los portugueses fracasaron una y otra vez ante la resistencia indígena. El detonante decisivo fue el ataque al engenho de Tracunhaém, que llevó a la creación de la Capitania Real de Paraíba en 1574. Recién el 5 de agosto de 1585 —día de Nuestra Señora de las Nieves—, una expedición comandada por Martim Leitão logró fundar de manera definitiva la ciudad de Nossa Senhora das Neves, futura João Pessoa, apoyándose paradójicamente en los tabajaras, que combatían contra los potiguaras. Poco después, João Tavares levantó el Forte São Filipe en la desembocadura del río, en honor al rey Felipe II de España, entonces también soberano de Portugal.
Como todo el Nordeste, la Paraíba organizó su economía colonial en torno a la caña de azúcar. La zona da mata y el litoral se cubrieron de engenhos trabajados por africanos esclavizados, y la ciudad —rebautizada Filipéia de Nossa Senhora das Neves en 1588— se consolidó como uno de los núcleos azucareros del imperio portugués.
Desde 1670, la ganadería extensiva empujó la ocupación hacia el interior semiárido, el sertão, dando origen a una sociedad de vaqueros, haciendas y una cultura ligada al ganado y a la resistencia frente a las sequías. Esa dualidad geográfica —el litoral verde y húmedo del azúcar, el brejo templado de la sierra y el sertão árido— marca hasta hoy la identidad paraibana.
Durante la expansión neerlandesa por el Nordeste azucarero, la Paraíba también cayó bajo dominio de la Compañía de las Indias Occidentales. Los holandeses llegaron a la región en 1625 y, tras varios intentos, tomaron la capital, que fue rebautizada Frederikstad —en honor al príncipe Federico Enrique de Orange—.
La ocupación se extendió hasta 1654, cuando los portugueses, con el apoyo decisivo de líderes locales, recuperaron el territorio dentro del proceso general de expulsión de los holandeses del Brasil. La resistencia paraibana quedó grabada en la memoria del estado como uno de los episodios fundacionales de su identidad.
En el siglo XIX la provincia adhirió a la independencia de Brasil y vivió las tensiones políticas del Imperio y la Primera República. El episodio que marcaría para siempre su historia ocurrió en 1930: João Pessoa Cavalcanti de Albuquerque, gobernador del estado y candidato a vicepresidente en la fórmula de la Alianza Liberal junto a Getúlio Vargas, fue asesinado el 26 de julio de 1930 en una confitería de Recife.
Su muerte fue uno de los detonantes inmediatos de la Revolución de 1930 que llevó a Vargas al poder y puso fin a la vieja república oligárquica. Ese mismo año, la capital —hasta entonces llamada Parahyba— pasó a llamarse João Pessoa en su homenaje. El lema del escudo del estado, 'Nego' ('me niego'), alude a la firmeza con que João Pessoa se rehusó a plegarse a la política dominante, y quedó como símbolo del carácter paraibano.
La Paraíba es una de las grandes cunas de la cultura popular del Nordeste. La literatura de cordel —esos folletos de poesía narrativa colgados de cordeles en las ferias—, el forró, la festa junina y la tradición del repente y la viola forman parte del alma del estado. La ciudad de Campina Grande, en el agreste, se disputa con Caruaru el título del 'mayor São João del mundo', una fiesta junina multitudinaria.
La Paraíba dio también a Brasil figuras intelectuales de primer orden: el poeta Augusto dos Anjos, autor de una obra tan singular como sombría; Epitácio Pessoa, presidente de la República entre 1919 y 1922; y el escritor José Américo de Almeida, autor de 'A Bagaceira', considerada pionera de la novela regionalista nordestina. El cineasta contemporáneo y buena parte de la música de raíz nordestina beben de esta matriz cultural.
El gran emblema geográfico de la Paraíba es la Ponta do Seixas, en João Pessoa: el punto más oriental de las Américas continentales, allí donde amanece antes que en cualquier otro rincón del continente. El Farol do Cabo Branco, obra art déco levantada sobre las falésias, marca ese extremo simbólico y se ha vuelto la postal del estado.
João Pessoa, además, presume de ser una de las ciudades más verdes del mundo, con el Parque Arruda Câmara y la Mata do Buraquinho, un fragmento de selva atlántica en pleno tejido urbano. Su litoral de playas serenas y arrecifes —Tambaú, Cabo Branco, Coqueirinho al sur— y el brejo fresco de la sierra completan una oferta que combina naturaleza, historia colonial y una intensa vida cultural popular.