Zoutenaaie was eeuwenlang het kleinste dorpje van België gebaseerd op het aantal inwoners. Reeds in 1111 was er sprake van "Saltanawa", een naam die later wijzigde tot Soutena (1228), Zoutena (1241), Soutena (1249), Zoutenay (1268),... De betekenis van deze naam zou zijn: een zoutwaterweide, waar lange tijd water op stond. 
In 1204 werd de onafhankelijke parochie opgericht. Er stond een kerk die toegewijd was aan Onze-Lieve-Vrouw-Hemelvaart, opgericht door Walther Zoutenay..Ze was 18 m lang en 6 m breed. De kerk werd verwoest tijdens de Franse Revolutie en de parochie hield op te bestaan in 1808. De bronzen klok van deze kerk hangt ter bezichtiging in de kerk te Eggewaartskapelle met ernaast een gebroken grafsteen opgegraven in 1962.

Een gedenkmonument is nu te bezichtigen in het centrum van Zoutenaaie(naast de parking van Restaurant Zoutenaaie).  

Bij de gemeenteraadsverkiezingen van 1848 kan men spreken van een merkwaardige gebeurtenis: vrouwen hadden toendertijd nog geen stemrecht, (vrouwen kregen die pas een eeuw later). Van de 23 inwoners waren er 5 mannelijke stemgerechtigden en elk van hen bracht een stem uit op eigen naam...In de krant "Standaerd van Vlaenderen" van 12 september 1848 stond te lezen dat Koning Leopold I Zoutenaaie met een bezoek vereerde en koos er zijn burgemeester, 2 schepenen en 2 raadsleden.

Een gemeentehuis vindt u er niet meer, de gemeenteraad vergaderde  trouwens in de keuken van de burgemeester. (Foto's te bezichtigen in de tearoom van Zoutenaaie). De laatste burgemeester was Daniël Kinget. Zoutenaaie moest haar zelfstandigheid prijs geven op 17 april 1971. De druk van de fusiegolf was te heftig, Zoutenaaie werd deelgemeente van Veurne met zijn  oppervlakte van 207 ha., en zijn 28 inwoners, momenteel zijn dat er zestien en 7 woonhuizen..

Omdat Zoutenaaie geen enkele drankgelegenheid bezat, kwam de stad Antwerpen in 1961 met een merkwaardig initiatief aanzetten:
Prof. K. C. Peeters, stadssecretaris van de Scheldestad liet twee noodwoonsten van het Kiel te Antwerpen verhuizen naar Zoutenaaie: aldus ontstond Tearoom Zoutenaaie.

De toenmalige schepen van onderwijs, Antoon Carton en zijn vrouw zorgden voor de gulle ontvangst tot hun pensionering in 1982.

Hun  zoon Fernand -huidige uitbater- volgde de Hotelschool te Koksijde en breidde de bestaande zaak uit met een prachtig restaurant.

 Burgemeester Oscar Kinget, vader van de laatste burgemeester Daniël,  deed in het jaar 1957 de officiële aanvraag een wapenschild als gemeentewapen te erkennen.Het werd toegestaan en bevestigd bij Koninklijk Besluit van 29 juli 1963 en ingehuldigd op 5 oktober 1963.Een zwarte leeuw op een gouden veld, met daarboven een groen schuinkruis. Achter het schild staat Sint-Bertinus. Het schild is geïnspireerd op een grafsteen uit de kerk van Wulveringem, waar de edele heer van Bampoele rust (+1540), heer van Soutenay. (Te bezichtigen in de Tearoom Zoutenaaie).