The Portuguese had been trying for years to hold this river mouth: five expeditions, four failures, a fort on the Paraíba burned within a year of being built. What finally worked was a treaty. On 5 August 1585 — the feast of Our Lady of the Snows, named for a legendary August snowfall in Rome — the Portuguese sealed peace with the Tabajara, led by Piragibe, against their Potiguara rivals. Settlement began on 31 October at the mouth of the Sanhauá River, and work started on the fortress on 4 November; some historians take that date rather than August as the true founding. Either way it makes João Pessoa one of the oldest continuously occupied cities in Brazil. A road was cut to join the hilltop Cidade Alta to the port below on the Sanhauá. In 1588 the place was renamed for Philip II, then ruling Portugal as well as Spain. By 1599, everyone was simply calling it Parahyba.

The Dutch took the city on their third attempt, walking in without resistance on Christmas Eve 1634 while the population fled inland. They renamed it Frederica — Frederikstad — for Frederick Henry, Prince of Orange. It held about 1,500 people and nineteen sugar mills at the time, and the invaders seized most of the mills. Elias Herckmans, who governed the captaincy from 1636 to 1639, left a description that still fits the topography: the city, he wrote, is surrounded by forest and cannot be seen by those approaching, except when one is already within it, unless one sails up or down the river. Those nineteen mills ran on the labour of enslaved Africans, and the long war fought over them — the Pernambuco Insurrection from 1645, the Dutch surrender in January 1654 — settled who would take the profits, not whether the system would continue. The Netherlands conceded the northeast formally only in 1661.

The historic centre was delimited in 1982 across 117 hectares and listed as national heritage in December 2007, the protected core covering 37 hectares and roughly seven hundred buildings through the Centro, Varadouro, Róger, Jaguaribe and Tambiá neighbourhoods. The range packed into that small area is what startles: baroque at the Third Order of São Francisco, rococo at the Carmo convent, mannerist lines at Our Lady of Mercy, neoclassical at São Pedro Gonçalves, then Art Nouveau and Art Deco fronts from the 1920s and 1930s around Praça Antenor Navarro. The old Hotel Globo is a museum now; its garden gives the best sunset in the city, out over the Sanhauá — the river the whole place began on, and the one the twentieth century turned its back on when it walked east to the beaches. The 2022 census counted 833,932 residents, and UNESCO named the city a Creative City for crafts and folk art in 2017.

During the 1992 Earth Summit in Rio, Mayor Carlos Mangueira announced that João Pessoa was the second-greenest city in the world, behind Paris. The claim has trailed the city ever since, and by the frankest accounts it was a publicity stunt with no methodology behind it. The odd thing is how close the underlying boast comes to being fair. More than seven square kilometres of forest sit inside the municipal limits, and at the centre of that is the Mata do Buraquinho, converted on 28 August 2000 into the Benjamin Maranhão Botanical Garden: about 515 hectares in all, 343 of them garden, and among the largest surviving fragments of urban Atlantic forest anywhere in Brazil. The Jaguaribe River rises inside it and runs out to the sea at the Cabedelo boundary. Eighteen interpretive stations line the two main trails.

In 1970 a state constitutional amendment capped buildings along the shoreline between Penha and Formosa beaches at two storeys, and the 1989 state constitution declared the whole Paraíba coast protected heritage and kept the ban in place. Walk down to Tambaú or Cabo Branco and the skyline steps down as it approaches the water rather than up, which almost nowhere else on this coast can say. The Hotel Tambaú — designed by Sérgio Bernardes, opened on 6 March 1971 — sits directly on the sand as a low circular drum, a building that could never be approved today and is loved for exactly that reason. Nine beaches lie inside the municipal boundary, most of them sheltered by a reef line about six kilometres out. And at Praia da Penha, the chapel raised in 1763 by a sailor named Sílvio Siqueira, who prayed through a storm at sea and made landfall there, still draws its annual procession from the historic centre, as it has for more than 250 years.