Periodo Bizantino, la dominazione Araba e l'arrivo dei Normanni

Dopo la caduta dell'impero romano la Sicilia subì le incursioni dei Vandali che con saccheggi e distruzioni ridussero allo stremo le città incontrate nel loro folle cammino, compresa Alicia. Ma le tribù barbare non riuscirono ad amalgamarsi con la popolazione conquistata e la loro effimera occupazione, sia per la durata che per i suoi modesti apporti demografici, non lasciò tracce profonde in nessun luogo. Quando nel 535 d.C. il generale Belisario ridusse la Sicilia sotto il dominio dei Bizantini, la popolazione godette un periodo di pace e di benessere e Alicia migliorò anche dal punto di vista urbanistico. Una testimonianza della dominazione bizantina potrebbero essere i resti della Basilica paleocristiana di San Miceli con i suoi tre pavimenti a mosaico sovrapposti di stile prettamente bizantino, come pure le tombe con corredi funebri, scoperti nel 1893 durante gli scavi condotti dall'archeologo Antonio Salinas, in una località poco distante dal paese. Poche sono le notizie che riguardano questo periodo di storia siciliana, tutte però ci parlano di una stremante politica fiscale che in tre secoli portò l'isola all'arretratezza economica e culturale. Dopo i Bizantini proprio sulle coste della Sicilia occidentale arrivarono i Musulmani.

Quando nell'agosto dell'830, con il loro sbarco a Mazara ed il progressivo espandersi nell'entroterra, gli Arabi conquistarono Halicyae non solo le attribuirono l'attuale toponimo Salemi ma, grazie anche alle loro avanzatissime tecniche di irrigazione , trasformarono quel vastissimo agro cha al loro arrivo dovette apparire abbandonato da Allah e dagli uomini in un fertilissimo giardino. Tanto che, già nel 1154, il geografo arabo Idrisi, incaricato da Ruggero il Normanno di redigere quella che possiamo chiamare la prima guida turistica della Sicilia, così descriveva la nostra Città: "Salemi è un casale molto vasto e popolato cui sovrasta un castello situato in eccelsa posizione. In questa località, vero tripudio di alberi e giardini, le acque sorgive sono copiose ed è diffuso per ogni dove il benessere..." Con la conquista normanna, sia per la sua posizione strategica sia per la presenza di una grande via di comunicazione, detta "Via di li jenchi", che attraversando gran parte del suo territorio rendeva più agevole il trasferimento dei cereali dall'entroterra siciliano verso i porti di Marsala, Mazara e Trapani, Salemi non fu concessa in feudo ma rimase legata al Demanio Regio. Condizione di considerevole vantaggio che i cittadini avrebbero difeso ad ogni costo contro i reiterati tentativi di infeudazione perpetrati nei secc. XVI e XVII dai Viceré spagnoli. Per ben tre volte, infatti, nonostante un "Privilegio" rilasciato da Carlo V recitasse che Salemi non sarebbe stata mai venduta ad alcun feudatario "quantacumque necessitate urgente", cioè neanche in caso di imprescindibili esigenze economiche, la Città rischiò di perdere la propria demanialità ma ogni volta i salemitani, avvalendosi di un "Capitolo", cioè di una legge emanata molti anni prima da Federico III d'Aragona, per cui le città in predicato di essere vendute potevano riscattarsi, preferirono pagare di tasca propria migliaia e migliaia di scudi pur di non perdere le importanti garanzie di legalità e democraticità che solo l'autorità del Re, e non certo la prepotenza di un feudatario, potevano offrire.