Bygget som kornmølle og i drift indtil 1939.

Normalt siger vi, at Danmarks ældste bevarede vindmølle står på Bornholm. Byggeåret for Bechs Stubmølle i Svaneke er lidt usikkert, men man regner med ca. 1630. Den bornholmske mølle har dog en konkurrent mht. æren som Danmarks ældste. På Samsø står Brundby Stubmølle, hvis byggeår også er lidt usikkert, men menes ligeledes at ligge i første halvdel af 1600-årene.

Brundby Mølle blev engang i begyndelsen af 1600-tallet opført på Endelave (lille ø mellem Samsø og Jylland).
Fra forarbejderne til Chr. V's matrikel kendes en beskrivelse fra 1681-83 af en mølle, der formodentlig er den nuv. Brundby Mølle. Det fortælles, at møllen tilhørte Christen Pedersen, der var smed i Tranebjerg på Samsø. Møllen var på dette tidspunkt ret forfalden. Den øverste sten i kværnen var gået i to stykker og samlet med en jernring, og såvel vinger som vindbjørn (bjælken, som vingeakselens leje hviler på) var helt "brøstfældige".
Da møllen ikke var til megen gavn, måtte øens beboere søge til Jylland for at få malet deres korn, eller hjælpe sig selv med deres håndkværne.
Den faldefærdige mølle blev solgt i 1683 og flyttet til Samsø, hvor den blev opstillet på bakken Dansebjerg syd for Brundby. Dansebjerg bestod af ler, som Brundbys bønder brugte til husbygning, derfor måtte møllen atter flyttes i 1817, hvor den fik sin nuværende placering på Kolhøj.
Før møllen kunne flyttes, måtte man jævne toppen af Kolhøj og anlægge en vej derop. Det kostede i 1817, 50 rigsdaler, hvilket har været noget af en formue. Møllen må således have haft en vis betydning, siden man ofrede dette beløb.
Interessant er det, at møllen altid har været ejet af folk af bondestand. I 1700-tallet kendes fire ejere, der alle var gårdejere i Brundby eller Ørby. Ofte var møllen ejet på part, dvs. at der var 2, 3 eller 4 ejere.
Da møllen blev flyttet i 1817 var Bertel Christensen, Brundby, ejer. Den sidste møller i Brundby blev møller Hans Kalledsøe, der startede som forpagter i 1898, og som så købte møllen i 1903. Driften ophørte i 1939, hvorefter institutionen "Kolhøj Stubmølle" tog over. Denne institution forsøgte at få møllen restaureret ved hjælp af penge indsamlet ved sommerfester i Brundby.
I 1961 blev møllen fredet, og i årene efter gik man i gang med at skaffe penge til en mere gennemgribende udvendig restaurering, der startede i 1965 med ingeniør Anders Jespersen, Nationalmuseet, som leder af arbejdet.
Vingerne kom på som det sidste i 1972. Ti år senere opstod en ny forening "Brundby Stubmølles Ejerlav", der fik møllen overdraget den 12. november 1983. Denne forening havde samlet pengene til den indvendige restaurering, så møllen var intakt ved overdragelsen.
(Kilde: Lise Andersen 'Møllen' nr. 3570/2005)

Der er Borde/bænke ved møllen og en dejlig udsigt.

Økomuseum Samsø har ansvaret for møllen. (2001)