最初の、本当の意味での征服遠征は740年に開始された。この年、かつて728年にもシチリア攻撃に参加したことのあったムスリムの王子ハビーブ（Habib）はシラクサ市を占領することに成功した。島全体の征服が計画されたが、チュニジアにおけるベルベル人の反乱（英語版）のために退却を余儀なくされた。2度目の攻撃は752年に、シラクサの再占領のみを目指して行われた。
エウフェミオスの反乱とムスリムによるシチリア征服詳細は「ムスリムによるシチリア征服（英語版）」を参照

826年、シチリアのビザンツ艦隊司令官エウフェミオス（英語版）は修道女に自分と結婚するよう強要した。皇帝ミカエル2世はこの件の噂を聞き付け、将軍コンスタンティノスにこの結婚を解消させエウフェミオスの鼻を切断するように命じた。エウフェミオスは反乱を起こしコンスタンティノスを殺害してシラクサを占領した。しかし彼は順次敗北を重ね、北アフリカへ逃亡した[1]。エウフェミオスはチュニジアを支配するアグラブ朝のアミール、ズィヤーダ・アッラーフ1世（英語版）に、将軍としての地位及び安全と引き換えにシチリアの支配権を差し出し、ムスリムの軍隊が派遣された[1]。

ズィヤーダ・アッラーフ1世はシチリア島の征服に同意し、エウフェミオスに毎年の貢納と引き換えにこの島を与えることを約束した。そして70歳になるカーディーのアサド・ブン・アル＝フラート（英語版）に征服が託された。アグラブ朝のムスリム軍団は、マツァーラ・デル・ヴァッロへの上陸後、歩兵10,000人、騎兵700騎、そしてエウフェミオスのものを加えて増強した船舶100隻を数えた。ビザンツ帝国軍に対する最初の戦いは827年7月15日にマツァーラ近郊で行われ、アグラブ朝が勝利した。

アサド・ブン・アル＝フラートはその後、島の南岸を占領し、シラクサを包囲した。1年間の包囲（英語版）と反逆の企ての後、彼の軍隊はドゥーチェ、Giustiniano Participazio率いるヴェネツィア艦隊に支援されてパレルモから派遣されてきた大軍を撃破することに成功した。しかし、ムスリムの軍隊内でペストが蔓延して多数の死者を出し、アサド・ブン・アル＝フラート自身も死亡すると、ムスリムたちはミネーオ城へ後退した。アサドの後にはムハンマド（在職：828年-829年）、次いでズハイル（在職829年-830年）がムスリムの指揮を引き継ぎ[12]、彼らは再び攻勢に出たが、カストロジョヴァンニ（現在のエンナ、この時エウフェミオスが死亡した）の征服に失敗し、マツァーラへ後退した。

830年、彼らは30,000人のイフリーキヤ人とアンダルス人の軍勢という強力な援軍を得た。アンダルスのムスリムの軍勢は同年の7月から8月にかけてビザンツ帝国の司令官テオドトスを撃破した。だが、再びペストがムスリムを襲い、マツァーラへの退却、さらにはイフリーキヤへの撤退を強いた。イフリーキヤ人部隊はパレルモ包囲に派遣され、831年9月に、1年にわたる包囲の後に同市を占領することに成功した[13]。パレルモはシチリアにおけるムスリムの首都となり、アル＝マディーナ（The City）と改名された[14]。

この征服の状況はシーソーのように一進一退を繰り返した。強力な抵抗と多くの内部紛争によって、ムスリムによるビザンツ領シチリアの征服には1世紀以上の時間が費やされた。シラクサは長期にわたってビザンツ領に踏み止まったが、878年に陥落（英語版）し、タオルミーナは902年に陥落した。そしてビザンツ帝国の最後の拠点は965年に占領された[1]。
シチリア島の総督アラブ・ノルマン（英語版）美術と建築は、西方的（Occidental）特徴（古典的な柱やフリーズなど） に典型的なアラビア風の装飾とカリグラフィーを合成させたものである。

アサド・ブン・アル＝フラートの跡を継いだシチリア島のムスリム支配者たちはワーリー（総督、w?l?）、場合によってはアミール（am?r）、アーミル（'?mil）と呼ばれ、アグラブ朝配下の総督としてシチリア島の支配に携わった[12]。シチリア島のワーリーは、現地のムスリムたちによって選出された後アグラブ朝の承認を得るか、あるいはアグラブ朝から直接任命された[12]。このシチリアのワーリー/アミールは、自らの意思で戦争と和平が可能な実質的な君主であった。しかし、アグラブ朝の影響力は大きく、その臣下という体裁は維持され続けた。当時シチリアで発行された貨幣にアグラブ朝の君主の名が刻まれ、フトゥバ（金曜日に行われる説教）においてはアッバース朝のカリフ（ハリーファ）と共にアグラブ朝のアミールの名が唱えられた事実が、アグラブ朝のシチリアにおける権威を証明している[15]。

シーア派指導者アブー＝アブドゥッラーがチュニジアの支配権を握り、アグラブ朝がファーティマ朝に取って代わられたという報せがシチリア島に届くと、シチリアのムスリムたちはアグラブ朝のシチリア総督アフマドを幽閉し、前総督のアリーを「ファーティマ朝の」シチリア総督として選出した[16]。こうしてシチリア島はスンナ派であるチュニジアのアグラブ朝、シーア派であるエジプトのファーティマ朝の権威に順次服した。しかし、イスラーム時代を通じて、スンナ派がシチリア島のムスリムコミュニティの主流派を占め[17]、パレルモの住民の（全てではないとしても）ほとんどがスンナ派であった[18]。ファーティマ朝とシチリアの関係はアグラブ朝の時と大きくは変化せず、フトゥバにおいてファーティマ朝カリフの名が唱えられ、総督はファーティマ朝によって任命されたが、シチリアは高い政治的自立性を保っていた[16]。

943年から947年にかけて、ファーティマ朝の厳格な宗教政策に対する宗派的反乱が北アフリカ全域で発生した後、ファーティマ朝の報復から逃れようとする難民の波がシチリアに向かって数度にわたって発生し、島内のスンナ派人口は更に増大した[19]。ビザンツ帝国はこの一時的な不和を利用して、シチリア島の東端部を数年間占領した。

947年4月25日に、パレルモで当時のシチリア総督イブン・アッターフに対する反乱が発生した[16]。ファーティマ朝のカリフ、イスマーイール・アル＝マンスール（英語版）は、混乱の収拾を託してカルブ家のアル＝ハサン・アル＝カルビー（英語版）（在職：948年-953年）をシチリア島のアミール（総督）に任命した。彼はひっきりなしに反乱をおこしていたビザンツ人を制御し統治することに成功した。ハサンは事が済んだ後、953年にはファーティマ朝の宮廷に呼び戻されたが、シチリア総督（アミール）位には彼の息子アフマド・ブン・アル＝ハサンが就任した[20]。アフマドも969年にファーティマ朝本国へ召還され、その後ハサンの解放奴隷ヤイーシュにシチリア支配が委ねられた[20]。しかし、間もなく無政府状態に陥ったため、再びアフマドがシチリアの支配者となり、その兄弟アブー・ル＝カースィム（英語版）が代理としてシチリアに派遣された[20]。970年にはアフマドが死去したため、アブー・ル＝カースィムが正式にシチリアのアミールとなり、以降ハサンの子孫（カルブ家）がシチリア総督位を世襲することが慣習化した[20]。これをカルブ朝（英語版）と呼ぶ。

カルブ朝の下で、11世紀に至るまで南イタリアへの襲撃が続けられ、982年にはオットー1世率いる「ドイツ」軍をカラーブリアのクロトーネ近郊で撃破した。アミール、ユースフ・アル＝カルビー（英語版）（在位：986年-998年）の即位と共に、着実な衰退の時代が始まった。アル＝アクハル（al-Akhal、在位：1017年-1037年）の下で王朝内の内部対立は激化し、支配家系内の様々な派閥がビザンツ帝国やチュニジアに新たに興ったズィール朝と同調した。1036年にはズィール朝の支配者アル＝ムイッズ・ブン・バーディース（英語版）はムスリムたちの反乱に介入すると共に、シチリア島の併合を試みて派兵した。この戦いの中でカルブ朝のアミール、アフマド2世が殺害され、ズィール朝の王子アブドゥッラーフがシチリア総督となった[20][21]。