Mogelijk is er in 1454 al een molen op Hoedekenskerke, want in dat jaar verkoopt Jan van Renesse van Zuylen ambacht en tienden aan Willem de Vriese van Oostende, waaronder "veren, molen en de molenstael, visscherie, vogelrie en de excisen ende al dat een ambacht toebehoort".

In 1753 was er in ieder geval sprake van een molen te Hoedekenskerke. Dit was een voor die tijd gebruikelijke houten standaardmolen. Deze molen staat getekend op de kaart van Hattinga. Op de molen rustte van oudsher al een cijns- of grondrente. Deze bedroeg ƒ 20,-- 's jaars ten behoeve van de ambachtsheren, ƒ 5,-- voor de Algemene Armen van Hoedekenskerke (het Burgerlijk armbestuur) en ƒ 5,-- voor de voogdij van de NH kerk. Waarschijnlijk is deze erfpacht overgekomen van de oude molen, want uit de koopakte van 1852 bleek dat deze molen belast was met “een altoos durende erfpacht” ten bedrage van ƒ 15,75 ten behoeve van de Grooten Armen en de Hervormde Kerk van Hoedekenskerke en ƒ 31,50 per jaar voor de gemeene Ambachtsheeren van Hoedekenskerke (in 1942 werd deze erfpacht voor ƒ 500,-- afgekocht).

In 1816 werd Pieter Klaasse eigenaar van de voorganger van de huidige molen.
Via advertenties in de Goessche Courant uit de vorige eeuw kunnen we grotendeels de eigenaren terugvinden. Op onderstaande lijst zijn de eigenaren en de molenaars weergegeven. Uit al die gegevens blijkt dat er in 1841 een herbouw heeft plaats gevonden en dat in 1875 de oude houten molen werd afgebroken. In het uitvoerig en beredeneerd jaarverslag over 1873 schrijft de secretaris onder hoofdstuk VIb “andere branden, dan die van den molen op 23 december 1873 hadden niet plaats”. Dit is in het hele archief de enige melding van de brand. Zelfs in het definitieve jaarverslag komt deze zin niet meer voor. Volgens Van Hoogstraten zou M.L. van Vessem van landbouwer J. Jonker op 1 april 1874 een stuk land gekocht hebben en daarop de huidige stenen korenmolen hebben gebouwd, waarna de oude molen werd afgebroken.

In 1936 stak molenmaker Van Riet (Goes) een nieuwe Potroede nadat een Fransen het tijdens het malen had begeven.

Tot 1964 werd beroepsmatig gemalen. De weduwe van de laatste molenaar, Bos, liet de molen in 1964 na aan D.A. de Bart, die deze in 1966 verkocht aan de Goesse ondernemer P. Dingemanse. Omstreeks 1965 had men buil, mengmachine en de 30 PK elektromotor op de begane grond al verwijderd.
In latere jaren ging de molen nog enige malen in andere handen over en dat steeds van personen die de molen wilden gebruiken voor recreatie. Om te kunnen dienen als vakantiewoning werd het gaandewerk deels uitgesloopt. Tenslotte stond de molen er vervallen en ontluisterd bij met één complete en één kale (en deels ingekorte) roede.

De komst van Dieter Borngräber uit Keulen betekende een doorbraak: onder deze nieuwe eigenaar volgde een grote restauratie, uitgevoerd door John de Jong uit Veldhoven. Op 19 juli 1995 werd een geheel vernieuwde kap aangebracht, de roeden gestoken en de staart aangehangen. Inmiddels was ook de omgeving verbeterd door het snoeien en kappen van een flink aantal bomen. Dat was hard nodig, want de molen was inmiddels sterk ingegroeid geraakt.

Na een aantal jaren viel het de Duitse eigenaar toch te zwaar om regelmatig naar de molen te komen. Vanaf 2005 nam de draaiactiviteit af. Vervolgens stond de molen een aantal jaren te koop en werd tenslotte verkocht aan een stichting die de Koutermolen als maalwerktuig wilde behouden. Daartoe werden ook enige mensen uit de omgeving opgeleid om de molen te laten draaien en voor publiek open te stellen.
Sinds 2007 draaide de molen regelmatig; vanaf 1 november 2008 wordt er wederom gemalen.

Opmerkelijk is het bovenwiel: de vellingstukken bevatten afdrukken van kammen en het lijkt aannemelijk, dat dit wiel eerder in een standerdmolen diende, mogelijk de voorganger van de huidige molen. In 2010 werd op zowel bovenwiel als één van de vangstukken het jaartal '1865' aangetroffen. Dat kan betekenen dat deze onderdelen inderdaad ouder zijn dan de huidige molen.

De bovenas was in 2007, vanwege de overhoekse ster op de walpenplaat en de gelijkenis met andere Zeeuwse assen, al geïdentificeerd als een Boddaert. In 2012 werd vlakbij de hals een (meegegoten) merkplaatje aangetroffen. 100% Boddaert dus! Vooralsnog neemt men aan, dat deze bovenas gegoten is vanwege de bouw in 1874.

In januari 2019 is begonnen met een grootscheepse restauratie. Eerst kreeg de molen vier nieuwe schoren, maar in maart begon men met de vernieuwing van een groot deel van de balkkoppen. Een fors aantal balken, donsbalk, diverse moerbalken en kleine kinderbalkjes, werden voerzien van kunstkoppen.
Toen dit klaar was werd begonnen aan de romp. 14.000 stenen moesten uitgekapt worden tot een diepte van soms twee rijen dik. Dit was, compleet met voegwerk, een flinke klus. Ondertussen voerde de molenmaker andere reparaties uit, zoals het stellen van de koning en alle wielen in de molen. Ook de oude motorkelder is aangepakt: die is nu weer waterdicht. Het laatste woord was aan de schilder.

Molenaars op de Koutermolen:
Jan Lambertus van Vessem (1874 - 1877)
Laurus van Strien (1877 - 1878)
Adriaan de Jonge (1878 - 1885)
Cornelis Remijn (1886 - 1892)
Marcus Verhulst (1893 - 1909)
Anthonie Moerland (1909 - 1910). Deze was ook molenaar te 's Heer Arendskerke.
Dingenis Dorst (afk. uit Wolphaartsdijk) (1911 - 1921)
Izaak Jacobsz. Sanders (1922 - 1927)
Willem Bos (1928 - 1952)
Dirk Andries de Bart (1952 - 1968)