Secondo la leggenda, Eliodoro conobbe uno stregone di origine ebraica, che lo iniziò alla magia. Costui gli consegnò un manoscritto magico che Eliodoro lesse in un cerimoniale magico tenuto di notte in cima ad una colonna per evocare il demonio. All'apparire del diavolo, Eliodoro avrebbe manifestato il suo desiderio di potere, e avrebbe contratto con il demonio un patto in base al quale avrebbe avuto esauditi i suoi desideri in cambio dell'abiura della sua fede cristiana.
Il mito a cui è legata la sua figura è quello del Liotru, cioè dell'elefante di pietra collocato oggi in Piazza del Duomo a Catania. Si raccontava infatti che lo avesse scolpito egli stesso, forgiandolo dalla lava dell'Etna, per poi cavalcarlo mentre compiva le sue magie. Il nome stesso di Liotru è una corruzione popolare del nome Eliodoro.
La tradizione popolare vuole che Eliodoro, dopo aver animato il suo elefante di pietra lavica, imperversasse per la città in sella all'animale magico, rendendo impossibile la vita dei suoi abitanti. Si narra che fosse in grado di acquistare qualsiasi mercanzia con pietre preziose ed oro, che però diventavano normali sassi nelle mani dei poveri mercanti.
Esistono diversi aneddoti sul potere di Eliodoro di Catania e sulla sua natura burlesca e dispettosa. Uno di questi vuole che egli abbia beffato il nipote del Vescovo facendolo puntare su un cavallo che altri non era che un demone evocato dal negromante, e che al momento della vittoria di quest'ultimo abbia poi rivelato a tutti i presenti la sua vera natura per poi scomparire nel nulla.
Arte
San Leone fa ardere il mago Eliodoro[1] di Giuseppe Patania (Palermo, 1780); è un bozzetto destinato alla chiesa di San Nicolò all'Arena di Catania. Ritrae il castigo inflitto dal vescovo Leone al Mago Eliodoro, per la pratica della magia giudaica.
San Leone, Eliodoro e il rogo (pittura murale) e La risparmiata di San Leo (bassorilievo)[2], rispettivamente del 1630 e del 1729, si trovano all'interno della Chiesa Parrocchiale di Saracena, in Provincia di Cosenza.