Wanneer de eerste molen in Hulst gebouwd werd is niet bekend, wel dat in de 13e eeuw reeds een drietal getijdemolens in werking was om graan te malen. In de 14e eeuw bevindt zich hier een drietal windmolens en nog één getijdemolen.
Op een plattegrond van Hulst van omstreeks 1560 staan vier standerdmolens in de binnenstad en directe omgeving afgebeeld. Op deze plattegrond staat ook de voorganger van de huidige molen, welke zeer waarschijnlijk in de 14e eeuw op het huidige molenerf is gebouwd.
In 1596 werd deze molen bij een belegering van de stad zodanig zwaar beschadigd dat een nieuwe molen gebouwd moest worden. In 1645 gebeurde dit opnieuw.
De nieuw gebouwde molen werd tussen 1700 en 1750 verplaatst naar de Molenberg aan het eind van de Overdamstraat en vervangen door een houten standerdmolen. De Molenberg lag op de plaats waar in de jaren 1950 de Keldermanspoort werd opgegraven.

In 1792 werd de houten molen vervangen door de huidige ronde stenen stellingmolen. Daar de molen als onderdeel van de vesting staatseigendom was, werd hij 's Lands Molen genoemd. Bij de molen behoort een bakkerij met drie ovens, welke zich ondergronds bevinden. De toegang hiervan is echter dichtgemetseld, waardoor deze bakkerij met bijbehorend gangenstelsel niet toegankelijk is.
De eerste molenaar van de nieuwe molen was Victor de Schepper (waaraan nog een fraai opschrift in de molen herinnert).

De molen is tot ca. 1931 in bedrijf geweest; de laatste jaren met hulp van een gasmotor.
Na 1940 raakte de molen sterk in verval. In 1944 verdween de stelling en tot overmaat van ramp sloeg in 1954 de bliksem in en brak brand uit. De schade, daardoor veroorzaakt, bleef echter beperkt.

Ingrijpen van het gemeentebestuur leidde tot de grote restauratie van 1956. Toen ook kreeg de molen de zeer toepasselijke naam 'Stadsmolen'.
De nieuwe roeden kregen het systeem Van Bussel. Eén koppel 15der kunststenen werd toen verwijderd, evenals een koekenbreker en een door een 20 Pk. gasmotor aangedreven maalstoel op de eerste zolder. Op de steenzolder zijn op 1 m. hoogte nog drie puntige nisjes voor het neerzetten van olielampen aanwezig. Ooit lag op de steenzolder (onder de vloer?) ook een pelsteen.

Op de Stadsmolen hebben diverse molenaarsgeslachten gemalen, waaronder de familie Lybaart van 1850 tot 1879 en vervolgens tot 1931 de familie Mariman. De familie Van Helsland was tussen 1946 en 1954, het jaar van aankoop door de gemeente Hulst, de laatste particuliere eigenaar.

In 1976 en 1984 onderging de molen herstelwerkzaamheden; in 1994/95 werd de kap grotendeels vernieuwd en beide roeden vervangen.

Eigenaren van de molen waren:
de Generaliteit (1792-1794)
het Franse bezettingsleger (1794-1808)
B. en N. van Waesberghe (1808-1818)
Isaac Paasse (1818-1831)
D. van Wijk (1831-1832)
D. Minderhout (1832-1840)
familie Lybaart (1840-1859)
J. van Vessem (1859-1879)
de families Mariman en Van De Walle (1879-1931)
familie van Helsland (1931-1954)
Gemeente Hulst (vanaf 1954)