Con la caduta dell’impero romano, inizia, a tutti gli effetti il periodo medievale. Mazara conosce prima la dominazione dei Vandali e dei Goti. Nel 535 d.C ha inizio il periodo bizantino, ma è proprio da Capo Granitola nel territorio di Mazara del Vallo, che ha inizio, nell'827, la nuova dominazione della Sicilia: quella degli arabi. Questi, danno grande importanza alla città. Amministrativamente, ad esempio, dividono l’isola in tre grandi parti: Val Demone, Val di Noto. e Val di Mazara, quest’ultima la più ampia delle tre. Sappiamo come gli arabi diedero grande impulso all’agricoltura siciliana, con l’introduzione di nuove essenze vegetali, basate su un metodo diverso d’irrigazione dei territori. Dalla nuova e più ingente produzione, si riavviano i commerci marittimi, stavolta con i popoli del nord Africa e la penisola iberica.
Con Ibn Mankut, oltre al porto attivo, Mazara diviene un Centro di studi islamici, dove si tenne l’insegnamento della  letteratura, della poesia, del diritto e delle religione.

Come in molti posti in Sicilia, Mazara del Vallo di aspra contesa tra arabi e l’esercito normanno. Nel 1072, questi ultimi, al comando di Ruggero d’Altavilla, ebbero il sopravvento, conquistando la città. Ma pochi anni dopo, nel 1075, gli arabi tornarono in città. . I saraceni erano guidati da Tenemisio,  nipote del re di Tunisi. Questo fino all’arrivo, di nuovo, di Ruggero, che, al comando dei suoi cavalieri, riprese Mazara. Il generale arabo Mokarta fu sconfitto. (oggi gli è dedicata l'omonima piazza del paese). Da questa vittoria, oltre ad una incisione sulla Cattedrale, nacquero leggende e storie narrate in tutta l’isola dai cantastorie. Il famoso etnologo ottocentesco, Giuseppe Pitrè, riuscì, nel suo lavoro,  a salvarne solo qualche strofa.

Con l’arrivo dei normanni si iniziò la costruzione da una parte, a scopo difensivo, di mura (che comprendevano solo una parte del centro storico) e l’ampliamento e la fortificazione dell’antico castello arabo(anche il centro storico è di derivazione araba), dall’altra di chiese, per riportare e rinvigorire i cittadini alla fede cristiana. Oltre all’edificazione della Cattedrale (tra il 1086 e il 1093), furono erette: la Chiesa di San Nicolò Regale,la Chiesa e il Monastero di San Michele, la Chiesa di Santa Veneranda, la Chiesa di San Francesco, la Chiesa di San Vito a Mare, la  Chiesa della Madonna delle Giummare e la Chiesa di San Martino (furono costruite anche chiese e chiesette nella campagna di Mazara).
Nel 1093 nacque la grande Diocesi di Mazara del Vallo. Essa comprendeva un’area vastissima, tanto da toccare le città di Palermo ed Agrigento.

Il re normanno  Ruggero I stabilì che le assise parlamentari si tenessero fossero itineranti. L’alto onore toccò anche a Mazara del Vallo, tra le prime. La cosa si protrasse fino al 1130, quando fu scelta come sede definitiva il palazzo reale di Palermo.
Il castello fu la maggiore opera costruita in questo periodo a Mazara. Posto nella zona sud-orientale, ricopriva l’area dell’attuale Villa Iolanda. Naturalmente era fornito di possenti bastioni e torri d’avvistamento, poste agli angoli dell’ampio riquadro. Erano denominate: : Torre di San Francesco, Torre Bianca e Torre delle Armi (detta anche Torre del Fiume),e nel restante angolo vi era, naturalmente, il castello. Quest’ultimo faceva parte di un più complesso sistema difensivo. Infatti, furono edificate delle fortezze alle spalle di Mazara, per difenderla da attacchi via terra. Erano situate vicino all’odierna Casa Santa (ad est), lungo la strada verso Marsala, (ad ovest) e  nei pressi di Tre Fontane (oggi del comune di  Campobello di Mazara.
Il castello fu residenza di molti Re, almeno fino al 1513 quando, ormai in rovina, non venne ritenuta  degna di interesse militare, e trasformata in prigione.
Del bellissimo castello oggi ne rimane solo una porta, perché, nel 1880, l’amministrazione di Mazara decise di demolirlo interamente.