Møllen har altid været tilknyttet herregården Nørholm (nu Nørholm Gods), som i middelalderen var et befæstet borganlæg. Sammen med borgen nævnes møllen første gang 1406, i en retssag, hvor borgens tilhørende jord tildømtes Kronen (dronning Margrethe I.). Vandmøllebygningen, uden jord, tildømtes kirken. Det lykkedes dog herregårdens ejere at tilbagekøbe jorden i 1524.
Det har været en travl mølle og den største i Ribe amt. Foruden herregården malede den korn for 215 gårde og 41 huse, som dækkede et område på 6.593 tdr. land
De nuværende bygninger er fra slutningen af 1700-tallet hvor godsejer Rosenørn Teilmann foretog en gennemgribende ombygning. I 1796 bliver der indlagt grubbe- og pilleværk og i 1916 monteres en turbine, som i mange år trækker en generator, der leverer strøm til borgerne i Thorstrup og omegn. Der har desuden i en periode været en smedje og et bageri tilknyttet vandmøllen.
Nørholm Vandmølle blev ubrugelig, da man under 2. Verdenskrig udvidede Karlsgårde Vandkraftværk. Man ændrede løbet af Varde å, fra Ansager til Karlsgårde Sø, og tog således det meste vand fra møllen. Siden har den været uvirksom, men er blevet vedligeholdt af Nørholms ejere. I 2008 blev en gennemgribende restaurering påbegyndt. Lokale håndværkere og møllebygger Jens Jørgensen har stået for arbejdet. bl.a. er de gamle tavl taget ned og bindingsværket genopmuret med specialfremstillede gule sten.
Karlsgårde Vandkraftværk er nu nedlagt og Varde Å ført tilbage til sit oprindelige løb, så der nu igen føres vand til møllen i en mængde, der gør det muligt at vise den i drift. Man har dog kun opnået tilladelse til den nødvendige opstemning i begrænsede tidsintervaller i månederne juli og august.