Alcune necropoli scoperte recentemente e numerosi oggetti delle varie epoche rinvenuti nel territorio randazzese hanno avvalorato l'ipotesi che Randazzo, sorta nella tarda epoca bizantina le IX secolo, sia stata edificata sulle rovine dell'antica Tissa. Randazzo acquistò notevole importanza durante la guerra del Vespro (1282), quando il Re Pietro d'Aragona vi insediò il proprio quartier generale per la guerra contro gli Angioini. Prescelta come dimora estiva dal Re Federico II d'Aragona (1303), nel 1312 vi nacque Guglielmo d'Aragona, al quale, all'età di otto anni, fu conferito il titolo di Duca di Randazzo. Nel XIV secolo ebbe capitoli civili e statuti propri, che furono successivamente soppressi nel 1345. Appartenne poi al Regio demanio, ma non ebbe sviluppo sensibile per la sua posizione vicina al cratere dell'Etna che la faceva ritenere sotto il costante rischio di colate laviche. Popolata da greci, latini e lombardi che conservarono fino a tempi recenti i propri dialetti e le loro chiese fu chiamata "Urbs Plena nel XVI secolo. Decadde sotto la dominazione spagnola e nella prima metà del XVIII secolo risultava abbandonata da oltre la metà della popolazione. Durante la II guerra mondiale fu l'ultimo caposaldo della resistenza tedesca in Sicilia, conquistato dagli alleati il 13 agosto 1943.