Con la fine dell’Impero romano, giunsero in Sicilia prima i Vandali, poi i Goti. Nel 535 d.C. l’isola passa sotto la dominazione bizantina. In questo periodo il territorio di Mistretta fu oggetto di razzie da parte di corsari arabi.
Un nuovo periodo di grande crescita da parte dei mistrettesi e dei siciliani in genere, lo si ebbe proprio durante la dominazione araba. Tra l’827 e il 1070, i nuovi conquistatori diedero impulso alle costruzioni, con metodologie edilizie nuove (a Mistretta venne ricostruito il cadente castellobizantino), l’introduzione di particolari metodi di coltura e l’importazione di specie vegetali, fin qui sconosciute in Sicilia (numerosi palmeti, come la palma dei datteri).
Nonostante quello che si pensi, i siciliani non furono costretti a divenire musulmani. Vi era una certa libertà di culto: chi voleva mantenere la fede cristiana doveva pagare una apposita tassa.

In epoca normanna (dal 1070) grande impulso ebbero le fortificazioni militari. A Mistretta, ad esempio, il castello arabo venne ingrandito e arricchito di nuove mura, che circondavano anche l’abitato. In particolare si conosce l’esistenza di grandi “bagli”, aggregazioni produttive e sociali, che rientravano all’interno delle mura difensive, da cui ebbero origine i “quartieri” cittadini,  individuabili, ancora oggi, nella struttura urbanistica del centro storico mistrettese. I resti delle mura difensive sono ancora oggi visibili nel Vico Torrione e lungo la Strada Numea sulla quale si apre la Porta Palermo (una delle due antiche porte che rimangono dell’antica Mistretta.

Con i Normanni ritornarono i grandi latifondi e la struttura baronale. Notizie sull’espansione dell’abitato sul monte del casyello di Mistretta, le abbiamo proprio grazie al documento in cui la cittadina viene donata da Ruggero d'Altavilla, nel 1101, al fratello Roberto, Abate della Santissima Trinità di Mileto Calabro.
Il castello di Mistretta rientrò varie volte nelle congiure di palazzo per la presa del potere in Sicilia. Nel 1082, fu Giordano, figlio (illegittimo) di Ruggero, a sfruttare l’occasione della momentanea assenza del padre, ad organizzare una congiura ai suoi danni, insediandosi al potere dell’isola. Nel 1160 fu la volta di Matteo Bonello, che, investito a capo della cittadina, provò a spodestare Guglielmo il Malo. Fu una cospirazione che come unico e solo risultato ebbe la morte del ministro Maione di Bari.
Ai tempi della dominazione sveva, Mistretta venne proclamata da Federico II “città imperiale”. Nel suo stemma venne inserita la rappresentazione di un aquila, propria delle effigie degli Hohenstaufen, casata tedesca degli svevi che governarono la Sicilia.