Tejn Stubmølle er sandsynligvis opført omkring år 1800 ved Årsballe, hvor den bar navnet Trebene Mølle. Omkring 1850 blev den flyttet til Tejn. Trods sin høje beliggenhed var der ikke vind nok, og ejeren i 1882, Peter Mikkelsen, tog møllen ned og genopførte den på et rundt fundament med gennemgang, hvilket gør, at den adskiller sig fra de øvrige bornholmske stubmøller.
Møller Peter Mikkelsen gjorde også møllen større ved at udvide både i højden og i dybden. Ved udvidelsen af møllen blev der blandt andet givet plads for et indvendigt hejseværk, som kunne hejse sække op gennem en lem i broloftsgulvet. Det er almindeligt, at hejseværkerne sad udvendig på lægavlen, som på både Bechs mølle og Egeby mølle. Også vingerne blev moderniserede fra split til vinger med regulerbare jalousier med fjedersvikning; en tidlig form for selvsvikning, hvor der ikke var iboret en ladestok i åsen. Vingerne løber "mod uret", modsat de fleste andre stubmøller.
Peter Mikkelsens søn drev møllen frem til 1941, hvor møllen var omgivet af beplantning og bebyggelse, der forhindrede møllen i at fungere. Herefter overtog Foreningen Bornholm møllen. Foreningen har vedligeholdt møllen, i nogle år hjulpet af en lokal støtteforening i Tejn.
Da en istandsættelse var nødvendig i begyndelsen af 2000-årene, besluttede man at flytte møllen til Landbrugsmuseet Melstedgård i 2006.
Her blev den i adskilt tilstand hovedistandsat, og rekonstrueret med fjedersvinkning, en ny -ældre -kværnsten.
Møllen blev indviet i 2009.