La città nacque con il nome Tauromenium, nome che ancora conserva anche se trasformato in Taormina, che significa abitazione sul Tauro, il monte su cui sorse. Lo storico Diodoro attribuisce l’assegnazione del nome alla città sia ai Siculi, che ai Greci. Secondo Pietro Rizzo, che ha scritto una storia di Tauromenium, furono probabilmente entrambi i popoli a chiamarla così.
Non mancano leggende che fanno derivare il nome da altre fonti. Una favoleggia di un Minotauro, che figura in monete antiche, al quale attribuisce la fondazione e il nome della città. Un’altra evoca due principi di Palestina, Taurus e Mena, che avrebbero fondato la città, dandole il nome Tauromena.
Attorno a Taormina fiorirono tante altre leggende. Alcune hanno per protagonista Pitagora, che avrebbe parlato nello stesso giorno a Taormina e a Metaponto, avrebbe fatto adottare a Taormina le leggi del catanese Caronda, avrebbe placato i furori erotici di un giovane taorminese suonando il suo magico flauto frigio. In realtà, Pitagora visse in un periodo storico nel quale Tauromenium non era stata ancora fondata.