Vi ved ikke, hvor længe der har stået en mølle på dette sted, men på et kort fra 1772 er "Kanehöys m." indtegnet. Denne mølle, som var en stubmølle, hørte under Gerdrup gods, og den nedbrændte i 1880.

Allerede året efter, i 1881, blev den nuværende mølle opført,(køreklar i 1882).  Det er en typisk "Hollandsk Mølle", dvs. en fast ottekantet træbygning, bygget på en firkantet muret grund. På toppen sidder en drejelig hat, hvorpå vingerne er monteret. Møllen er selvkrøjende, dvs. den drejer selv vingerne op mod vinden.

I 1884 fik møller Carl Kristiansen fæstebrev på møllen, som stadig tilhørte Gerdrup gods, og ved hans død i 1901 fik sønnen Hans Kristiansen overdraget fæstet. Han købte møllen til selveje i 1916. Dennes søn Knud Kristiansen, overtog møllen i 1934 og drev den til 1961, hvor sønnen Hans Kristiansen overtog og drev møllen, til han ved et gavebrev i 1982 skænkede den til det nyoprettede Kanehøj Møllelaug.

Her har - som ved andre møller - været tilknyttet et bageri. Kanehøj Brødfabrik var en kendt virksomhed på egnen, indtil Hans Kristiansen lukkede den ved sin pensionering i 1992

Kanehøj Mølle har været forskånet for de store katastrofer siden 1880, og møllen er derfor intakt i dag. Men et par mindre katastrofer har der været. I 1940 og igen i 1963 er hat og vinger blæst ned og ødelagt, begge gange fordi møllen kom i "bagvind", dvs. vinden er pludselig vendt og hatten har ikke kunnet nå at vende hurtig nok - og en storm, der "kommer bag på" møllen, kan altså rive hat og vinger ned.