تمسّك البيزنطيون بقصريانة المحصن لكن العرب لم ييأسوا، ففي سنة 834 م قاد ابو فهر حملة عسكرية لاقتحام القلعة وكانت خسائر البيزنطيين كبيرة كما قام بغزوتين ونجح في اسر ابن البطريق البيزنطي وارسل وحدة عسكرية إلى طبرمين Taormina لكن لم يكن احد يتصور انه سيموت على ايدي جنوده الذين أعدوا له كمينا وقتلوه وانضموا للجيش البيزنطي! عندما علم زيادة الله الاغلبي باغتيال قائده ابو فهر عين الفضل ابن يعقوب قائدا جديدا للجيش وتوجه إلى سرقوسة وجمع غنائم كثيرة ثم توجه إلى قصريانة ثم ارسل أبا الأغلب ابراهيم بن عبدالله أميرا جديدا للجيش .
كانت اولى إنجازات القائد الجديد تجهيز أسطول بحري قادر على أن يصمد في وجه الاسطول البيزنطي وبعد أن تمكن من تجهيز أسطول ضخم توجه نحو الساحل الذي كان تحت سيطرة البيزنطيين وفي مواجهة شرسة نجح في اسر عدد من البيزنطيين ووصل إلى جزيرة قوصرة Pantellaria.
وبالتوازي مع استهداف السواحل قام الجيش العربي بغزوتين في جهة جبل النار سنتي 835 و836 م وحققوا غنائم كثيرة ويقال أن الرقيق بيع بأرخص الأثمان وفي العام نفسه توجه ابو الأغلب إلى معقل قسطلياسة Castellucio وحققوا غنائم كثيرة كما هاجم الفضل بن يعقوب الجزر الأيولية واستولى على بعض الحصون منها دنداره Tindaro وفي سنة 837 م وجه ابو الأغلب جيشا إلى قلعة قصريانة المنيعة بقيادة عبدالسلام بن عبد الوهاب ونجح العرب في دخول القلعة وأصابوا الكثير من الغنائم لكنهم فشلوا في الاستيلاء على قصبتها فعقدوا هدنة وغادروا قصريانة التي عادت إلى السلطة البيزنطية في بلارمو.
ولكن تم الاستيلاء على قصريانة في ولاية العباس بن فضل إذ أقام العرب ثلاثة اشهر حول قصريانة وكان من بين الذين تم أسرهم رجل له قيمة رمزية عند البيزنطيين وعندما أدرك انه سيقتل طلب من العباس أن يبقى مع المسلمين ووعده بأن يساعده على دخول المدينة المحصنة وارسل العباس بن فضل مع الرجل ألفي فارس فدلهم على مدخل المدينة فدخلوها بعد مقاومة بسيطة وفتحوا الأبواب فدخل العباس وبنى حال دخوله مسجدا وكان اليوم جمعة فنصب منبرا وخطب في الناس وقتل الكثير واسر عددا من بنات البطارقة بحليهن وأصاب فيها « ما يعجز اللسان عن وصفه» وأهدى إلى المتوكل من سبيها وكان رد فعل القسطنطينية على سقوط قصريانة قويا إذ أرسلت أسطولا ضخما لكن المسلمين نجحوا في القضاء عليه.
