Le prime notizie certe intorno al territorio di San Teodoro risalgono al 23 maggio 1303, quando Federico III d'Aragona, concesse il feudo a Giordano Romano. Morto il Giordano il feudo passò nelle mani della moglie Margherita Campulo e successivamente nelle mani della famiglia di quest'ultima, prima alla maggiore delle due figlie, Isolda, che a morte lo lasciò alla sorella minore, Floretta. Dopo la morte di Floretta il feudo passò alla zia Bella che il 6 ottobre del 1402 lo donò al nipote Paolo Campulo. A Paolo succedette, dopo il primogenito, il figlio minore Geronimo, nel 1510.
Nel 1633 Giacomo Campulo fu onorato del titolo di Marchese di San Teodoro. Nel 1674 la Regia Corte s'incorporò il titolo e lo vendette a Francesco Maria Bruno nel 1678; in seguito il titolo venne restituito alla famiglia dei Campulo ma si estinse dopo due generazioni. Il 17 ottobre 1678 il territorio di San Teodoro venne acquistato da Mario Parisi col titolo di Barone; il figlio Francesco vendette il feudo a Diego Brunaccini che fu il primo ad essere nominato Principe di San Teodoro.
Nel 1692 il Principe fece costruire la prima casa del paese e la chiesa dedicata a Maria SS. Annunziata.
L'insorgere della malaria costrinse gli abitanti del paese a trasferirsi stabilmente dalla contrada Fondachello alle falde del monte Abate, luogo più salubre; si determinò così l'incremento del paese che fu messo sotto la protezione di San Gaetano.
San Teodoro, dopo la divisione musulmana della Sicilia, apparteneva alla Val Demone; ma dopo l'emanazione del regno della Sicilia, che modificò l'antica divisione, San Teodoro venne assegnato all'Intendenza di Messina e al Distretto di Messina.
I primi registri del Comune risalgono al 1820, per il decennio che va dal 1929 al 1939, gli abitanti santeodoresi fecero parte del comune di Cesarò. Ritornò libero Comune nel 1939.
Nel 1908 venne istituito l'ufficio postale, nel 1911 quello telegrafico. Nei primi anni Cinquanta San Teodoro raggiunse una punta alta di abitanti, grazie anche alla costruzione della diga d'Ancipa che assicurò lavoro a molti operai.
Ma successivamente cominciò l'esodo verso il Nord-Italia, o altre zone,  con maggiore possibilità di impiego.