Si l'on retrouve des petits postes de traite fortifiés dans le sud et dans le nord-est de la province au 17e siècle, il faut attendre au 19e siècle pour que le Madawaska connaisse ce type de construction. En effet, à l'époque, la région est essentiellement occupée par les Amérindiens Malécites (Wolastoqiyiks). Elle sert surtout de lieu de passage et de portage entre les établissements français de l'Acadie et ceux de la vallée du Saint-Laurent.

La première construction fortifiée serait donc celle du Fortin du Petit-Sault. « Petit-Sault » était d'abord le nom d'un escarpement rocheux sur le cours de la rivière Madawaska et qui servait à le différencier de la chute de près de 25 mètres, le « Grand-Sault », située 65 kilomètres plus loin. À partir de 1820, le village situé près de la petite chute prend aussi le nom de Petit-Sault. Ce n'est qu'en 1850 que Petit-Sault devient Edmundston, en l'honneur du lieutenant-gouverneur du Nouveau-Brunswick de l'époque, Sir Edmund Walker Head. À l'époque où Edmundston s'appelait toujours Petit-Sault, la frontière entre le Maine et le Nouveau-Brunswick était source de conflits. Le traité de Webster-Ashburton de 1842 va tracer définitivement la frontière officielle, mais les conflits vont durer encore quelques années.

En 1841, un fort est érigé à Petit-Sault, en vue de protéger le territoire, mais aussi d'assurer la ligne de communication entre Québec et Fredericton. Le fort était situé à une hauteur de 150 pieds (45 m) et dominait les vallées de la rivière Saint-Jean et de la rivière Madawaska. Occupant une position stratégique et de construction solide, le fortin avait une fondation de pierre de trois pieds (90 cm) d'épaisseur sur laquelle reposaient deux étages, faits de pièces de pin de 15 pouces (40 cm) de côté. Malgré tout, le fortin est endommagé par la foudre en 1855 et finalement démoli en 1868.

Une maquette à l'échelle du Fortin du Petit-Sault se trouve au Musée historique du Madawaska, à Edmundston. De plus, avec le financement du gouvernement fédéral et les Papiers Fraser qui s'engagent à fournir le bois nécessaire, la reconstruction du Fortin du Petit-Sault à son emplacement original débute en 2000. Il est aujourd'hui un lieu d'interprétation historique fort intéressant.