Le site de la pousada chez roni

Au début du XVIe siècle, les Français connaissaient déjà la région et établirent de bonnes relations avec les indiens potiguaras. Ces corsaires avaient pour principal but l'exploitation du bois de pernambouc. Le Portugal établit sa souveraineté sur la région en établissant la capitainerie d'Itamaracá mais celle-ci sera abandonnée par son propriétaire. Ce n'est qu'en 1585 que João Tavares conclut une alliance avec les indigènes. Cette alliance permit la construction à l'embouchure du fleuve Paraíba, le fort São Felipe et la fondation de la colonie de Nossa Senhora das Neves, aujourd'hui João Pessoa, et conséquemment l'expulsion des français. La paix avec les indigènes fut rompue en 1599, après l'épidémie de variole qui décima la population autochtone.
Entre 1634 et 1654, la région fut occupée par les Hollandais jusqu'à leur expulsion par André Vidal de Negreiros. Dans les années suivantes, de nouveaux conflits avec les indiens provoquèrent des révoltes qui nécessitèrent une intervention de la métropole (le royaume du Portugal). En 1753, la région fut subordonnée à la capitainerie de Pernambouc, de laquelle elle se sépara de nouveau en 1799. La Paraíba participa à la Révolution de 1817 ainsi qu'à la confédération de l'Équateur (1825).
La province est devenue État lors de la proclamation de la république, le 15 novembre 1889.
En 1930, João Pessoa, gouverneur de l'État, est nommé vice-président de la République au sein du gouvernement de Getúlio Vargas. Son assassinat la même année fut l'étincelle qui déclencha la révolution de 1930.