Man schätzt, dass die Mühle zwischen 1550 und 1600 erbaut wurde. Am 10. Dezember 1759 verkauften die Erben des Freiherrn von Wentz ihre Güter, darunter auch die damalig noch als Ölmühle fungierende Mühle. Zwischen 1806 und 1813 hatte sie dann die Funktion einer Tabakmühle, in der Tabakblätter aus der Pfalz zu Kautabak zerschnitten wurden.
Im Jahr 1816 ließ Graf Clemens Wenzeslaus die Mühle zu einer Kornmahlmühle umbauen. Es folgten danach mehrere Besitzerwechsel. Ihren Namen hat die „Hein’s Mühle“ von den Eheleuten Elisabeth und Paul Hein, die in 1898 zahlreiche Umbau- und Erweiterungsmaßnahmen starteten. Das Müllerbuch verzeichnet den letzten Mahlgang am 11. April 1961. Im Jahr 1983 stellte die Kreisverwaltung die Mühle unter Denkmalschutz. Am 22. Juli 1986 kaufte die Stadt Bendorf die Mühle, um sie einer musealen Nutzung zuzuführen.
Im März 1987 hatten Fritz Bode und Fritz Pösch aus dem Kreis der Vereinigung der „Sayner Heimatfreunde“ die Idee, die Mühle wieder gangbar zu machen und boten der Stadt unentgeltlich ihre Hilfe an. Die drei „Sayner Mühlenmänner“ waren damals Fritz Boden (63), Franz Lenßen (69) und Emil Holler (68). Am 29. Oktober 1987 wurde dann der „Förderkreis Hein’s Mühle“ gegründet, der sich fortan für Betrieb und Gästeführungen einsetzte. Am 26. August 1988 wurde die Hein’s Mühle dann als Mühlenmuseum eröffnet: Die Anlage war komplett funktionstüchtig.