La conquista da parte dei Normanni della Sicilia, non portò all’immediata sostituzione delle abitudini musulmane. Per un secolo, ad esempio, la lingua araba continuò ad essere utilizzata come lingua del governo e dell'amministrazione statale. Quando la conquista dell’isola fu completata, i normanni, tuttavia, imposero ai dominatori precedenti di scegliere tra la partenza volontaria o la sottomissione all'autorità cristiana. La religione islamica vieta di vivere sotto autorità non-musulmane, sempre se questo può essere evitato. Molti partirono, ma poiché non tutti avevano i mezzi per affrontare il viaggio, si poneva il quesito di come concordare la duplice scelta. Una fondamentale  fatwa dell'imam al-Mazari, permise il soggiorno di musulmani in dar al-harb, sempre se questi potevano vivere godendo del portato della Legge islamica.
Il Regno di Sicilia di Ruggero II fu caratterizzato, così, come multietnico e religiosamente tollerante. Vivevano concordemente sotto di esso normanni, ebrei, arabi musulmani, greci bizantini, longobardi e siciliani originari. Ciononostante, i normanni portarono avanti ininterrottamente un’azione di “latinizzazione” (la conversione delle popolazioni siciliane al Cristianesimo romano). Nel successivo sviluppo storico la tendenza fu quella di riassorbire le genti musulmane, dapprima con una localizzazione delle comunità arabe, nella metà sud-occidentale dell'isola, mentre il nord-est era cristiano. Dopo la morte nel 1189 di re Guglielmo il Buono le aggressioni contro i musulmani, sempre più ripetute, infransero la possibilità di coesistenza fra le etnie.

Nel 1198 in Sicilia, dopo la morte di re Enrico VI e poi di sua moglie Costanza, si verificarono disordini, scontri e rivolte, tutte collegate alla guida politica, tra forze rivali tedesche e papali. Inizialmente i ribelli musulmani sostennero il tedesco Marcovaldo di Annweiler. Il papa Innocenzo III, pur continuando trattative con la comunità araba siciliana, accusò Marcovaldo di essersi legato con un diabolico accordo con i Saraceni. Non passò molto che i rivoltosi arabi si organizzassero in una insurrezione propriamente musulmana. Guidati da Muhammad b. Abbād (denominato " il principe dei credenti"), presero il controllo di  Jato, Entella, Platani, Celso, Calatrasi, Corleone, Guastanella e Cinisi, fino all’occupazione di parte della Sicilia occidentale.
La successione normanna, in questo periodo, aveva  Federico II ancora bambino (sotto la protezione del papa). Quando il re normanno crebbe e prese lo scettro reale, inviò truppe a scardinare la rivoluzione musulmana. Conquistate diverse fortezze ed aree siciliane, il re, nel 1223, ordinò le prime deportazioni di musulmani a Lucera. Riprese il dominio reale di Malta e Gerba, evitando il pericolo di aiuti esterni ai rivoltosi.
Nei secoli seguenti gli Hohenstaufen e poi gli Angioini ed Aragonesi continuarono l’impegno di latinizzazione delle popolazioni siciliane. Vennero praticamente cancellate le comunità arabe e l'ortodossia greco-bizantina (sostenuti nell’opera dalla Chiesa romana).
Del 1240 sono le ultime deportazioni di musulmani a Lucera.