Regalbuto nacque in epoca musulmana; fu un casale (in arabo Butah) formatasi alla prima stazione (arabo Rahal) sulla strada Catania - Palermo, dove ne derivò il nome di Rahl-butah, cioè stazione del Casale. Gli abitanti erano tutti saraceni, come dice esplicitamente il Conte Ruggero nella denominazione al Vescovo di Messina (1090), che porta ancora il titolo di Conte di Regalbuto, e riscuote un censo, gravante su molti fonti, derivate dall'antica decima. Il Conte stabiliva pure che Butah anche ecclesiasticamente facesse parte della diocesi di Messina, quantunque si trovasse nel territorio della diocesi di Catania:

« se avverrà in futuro che lo stesso Casale venga ad essere abitato da Cristiani, e che siano esatte chiese in esso dal Vescovo di Messina »…

 Quest'ultima volontà, però, non fu adempiuta: Regalbuto dipese sempre da Catania, e solo nel 1556 il papa Paolo IV concesse al Presule di Messina il privilegio di fare uso delle prerogative di un Vescovo giurisdizionale durante la sua permanenza a Regalbuto. Il paesetto era allora sul declivio della contrada Monte; sulla sommità fu costruita la fortezza, sulle cui rovine venne eretta la chiesa di San Calogero (oggi un rudere), che dà il nome al monte (i ruderi della chiesa hanno l'aspetto di una torre mozzata, che è caratteristica del panorama di Regalbuto). Alcune scritture conservate nell'archivio della Matrice affermano che essa sia stata la prima Chiesa Madre del paese, edificata e dotata dal re Manfredi di Sicilia. I suoi procuratori intrapresero nel 1700 una vivace lite giudiziaria contro il vescovo di Catania per sottrarre la chiesa alla sua giurisdizione ritenendola Cappella Palatina, dipendente quindi dal Cappellano Maggiore. Per la sua fedeltà a Manfredi, Regalbuto fu distrutta nel 1261 dai centuripini che si erano ribellati allo Svevo.