Den første oplysning om møller i Ulsted kan dateres til 1613. I 1802 var der 18 stubmøller og 2 hollandske vindmøller i Kjær Herred. Dette tal var meget stort i forhold til resten landet. 

På dette tidspunkt var der 2 møller i Ulsted, af hvilken grund den nuværende Ulsted Mølle blev kaldt Vestre Mølle.

Ulsted Mølle var tidligere en stubmølle, men blev senere ombygget til en hollandsk vindmølle. Oprindeligt lå møllen lidt nordligere end i dag, og den blev først flyttet til dens nuværende placering i 1880, ifølge folkesnakken fordi møllerkonen var ked af spektaklet fra møllen, men flytningen skyldes nok snarere vindforholdene.

Den sidste møller ved Ulsted Mølle var N. P. Nielsen, der drev denne frem til lukningen i 1953. På initiativ af møller N. P. Nielsen lykkedes det længe at bevare Ulsted Mølle, dels fordi Ulsted Borgerforening gik ind og tog vare på møllen, og dels fordi Ulsted Sparekasse ydede økonomisk bistand til vedligeholdelsen.

I 1969 overdrog N. P. Nielsen Ulsted Mølle til den daværende Ulsted Kommune

Den 8. januar 2005 blæste hatten af Ulsted Mølle og den gennemgik en omfattende renovering, således at den igen kunne køre med sejl. Imidlertdig er træværket medget dårligt, og der forestå en meget stor restaurering af møllen.