Gallodoro trova antichissima origine in età greca, in un insediamento abitativo sito in prossimità delle contrade Margi e S. Anna, che secondo tradizione popolare veniva chiamato Bocena. I ritrovamenti di monete, cocci di brocche e vasellame vario oltre che di tombe, hanno fatto ipotizzare anche la possibile ubicazione della città di Kallipolis, fondata dai calcidesi della vicina Naxos, prima colonia greca di Sicilia.
L’attuale borgo di Gallodoro risale al periodo medievale, allorché si formò in epoca bizantina il primo nucleo abitativo intorno alla chiesa rurale di S. Teodoro Martire. Ubicata in un luogo di passaggio tra la parte bassa e quella alta della cosiddetta Vallis Aurea, nome dato dai Romani alla valle (o per l’ubertosità del luogo o per l’esistenza di giacimenti d’oro) e da cui deriva l’odierna denominazione di Gallodoro, la chiesa divenne nel corso dei secoli il luogo di culto principale della comunità rurale di Gallodoro. Da questo polo insediativo si sviluppò, nel corso dei secoli, l’impianto urbano che si dispiega oggi in maniera tale da assumere la forma di cavea di teatro, con le edifici abitativi addossati l’uno all’altro tra scorci suggestivi e di rara bellezza rurale.
Fino all’alba dell’età moderna, Gallodoro apparteneva al territorio della città demaniale di Taormina.
Anche se, secondo Anzalone, signore di Gallodoro fu Nicola Crisafi, Maestro Razionale del Regno e Strategoto di Messina nel 1422, da questa data fino al 1634 troviamo Gallodoro con il suo territorio aggregato alla Secrezia di Taormina. Sotto il regno di Filippo IV, il territorio di Gallodoro fu smenbrato da quello di Taormina e venduto dalla Regia Corte a Donna Francesca Porzio, moglie di Don Francesco Reitano, entrambi di Messina; e ciò per il prezzo di onze 13.240, con atto stipulato nell’ufficio di Luogotenente di Protonotaro, in data 23 febbraio del 1634. Qualche giorno dopo, inoltre, la neomarchesa di Gallodoro ottiene dal viceré Ferdinando Afan de Ribera, duca di Alcalà, la “licentia populandi” di Castellaci, aspro acrocoro nelle vicinanze del paese. Erede legittimo di Donna Francesca Porzio fu il figlio Don Antonio Reitano che, investito il 29 gennaio 1641, divenne Marchese di Gallodoro. Questi prese parte attiva nella famosa rivoluzione di Messina (1673-1678) a favore della fazione dei Malvizzi seguace dei Francesi contro il governo spagnolo. Nel momento in cui le armi spagnole ebbero il sopravvento e ripristinarono il loro potere, gli insorti ebbero la peggio tra arresti, esili e confische. Analoga sorte toccò a Don Antonio e Don Placido Reitano, rispettivamente padre e figlio, che dovettero subire l’onta dell’esilio e la confisca del loro patrimonio fra cui anche il Marchesato di Gallodoro, ed infine furono costretti ad abbandonare il proposito di costruire in seno al territorio di Gallodoro, il paese di Castellaci.
La Regia Corte vendette la terra di Gallodoro a Stefano Oneto e il titolo di Marchese di Gallodoro ad Agesilao Bonanno, ma il Re non approvò tali vendite come risulta da una sua ordinanza emessa a Madrid il 24 novembre 1677, resa esecutoria nel Regno a partire dal 27 giugno 1678. Da fonti storiche apprendiamo che lo Stato e la terra di Gallodoro fu comprato nel 1679 da Don Giuseppe Vigo, da questo momento in poi, per tutto il Settecento e fino agli inizi del successivo, Marchesi di Gallodoro furono esponenti dell’illustre famiglia Vigo di Acireale.
Tra la fine del Settecento e nel corso dell’Ottocento in seno al territorio di Gallodoro si sviluppò, dal punto di vista socio-economico, la frazione di Letojanni. Con il trasferimento nel paese di marina delle più importanti famiglie di Gallodoro, che costruirono i loro rispettivi palazzi, Letojanni rivendicò e ottenne nel 1879 il trasferimento della sede municipale dal centro collinare alla marina, con conseguente ridimensionamento di Gallodoro. Solo dopo decenni di lunghe battaglie, la comunità di Gallodoro riuscì a staccarsi da Letojanni e a realizzare la tanto agognata autonomia comunale, sancita dalla legge regionale del 26 novembre del 1952.