Летом следующего года аглабиды — африканские арабы-мавры, жившие на территории современного Туниса, воспользовались мятежом заместителя сицилийского стратига — турмарха Евфимия. Этому типу грозило разжалование и положенное по закону усечение носа за то, что он похитил и заставил некую монахиню святотатственно вступить с ним в брак. Он сбежал от ее разгневанных братьев и царского правосудия в северную Африку и там склонил эмира Кайруана организовать нападение на Сицилию и признать его императором. Самозванец вскоре погиб от рук ромеевских послов из Кастоджованни, неожиданно убивших его во время переговоров о сдаче города, но с этой необычной уголовно-романтической истории началась эпоха войн за благодатный богатый остров.
Арабы-аглабиды высадились на Сицилии с большим войском, начав шаг за шагом завоевывать ее, несмотря на отчаянное сопротивление ромеев, нехватку продовольствия и эпидемию чумы. Взяв после одиннадцатимесячной осады крупный сицилийский город Панорм (Палермо) в 831 г., они сделали его новой столицей эмирата. Греческое население бежало в восточную часть острова, источники доходов с которого для византийцев заметно сократились. Со своей новой базы мусульмане совершали рейды на побережье Адриатики, восток и юг Италии, в Апулию и Калаврию, а в крупнейших италийских портовых городах-крепостях Таренте и Бари основали эмираты. Могущество Ромейского царства в Средиземном море, и, особенно, на Адриатике, было самым серьезным образом подорвано.
Общее положение, ухудшившееся после гражданской войны 820–825 гг., удалось несколько выправить лишь к 840 г., когда Феофилом, последним василевсом-иконоборцем, постоянно заботившемся о государственной безопасности, была удачно проведена военная реформа, которой предшествовали военно-территориальные преобразования, выделение новых фем, главным образом на северном, понтийском побережье Малой Азии и на тесно связанном с ним Крымском полуострове. Погрязшие в раздорах арабы больше не могли, как прежде, выставить единую армию, и теперь ромеям противостояли войска отдельных эмиров, начальствовавших над приграничными крепостями. Мусульмане все больше переходили к обороне. В любом случае иконоборская эпоха прошла для ромеев на редкость бурно. Казалось, будто Господь одновременно и губил, и спасал Империю.
Эпоха иконоборства стала самым ярким и противоречивым периодом в истории византийских «темных веков». С одной стороны, внутренняя смута и распри, вспышки фанатизма и жестокие расправы, насилия над инакомыслящими любого лагеря, опустошительная, кровавая гражданская война. Трудно поверить, что могло быть такое взаимонепонимание между теми, кто подвизался ради одной и той же цели, исповедовал одну веру. Иконоборские императоры стремились подчинить Церковь своей воле, пренебрегали догматическими канонами, шли на установление жесткой диктатуры, вели репрессии внутри страны и непрерывные войны за ее пределами, поначалу не особо заботясь о развитии культуры, образования.
С другой стороны, на это же время приходятся развитие эффективного фемного строя, военных структур, разрастание системы провинциальной администрации, блестящие успехи ромейского оружия и самые большие победы над болгарами и арабами. Несколько драматических неудач не пошатнули положения. Невзирая на некоторую формальную децентрализацию, начавшуюся уже с VII в. вследствие развития, эволюции фемного строя, самодержавие все же укреплялось. В Ромейском царстве шел медленный процесс консолидации. Устойчиво держалось сельское хозяйство хоритов, кинонов, еще не познавшее губительного засилья знати. Не замирали торговля, промыслы, мелкая предпринимательская деятельность. После сокращения доходов государства до 15 млн. солидов в середине VII в. постепенно наметился их подъем к середине IX в., когда они достигли 30 млн. солидов. Василевсу Феофоилу даже удалось скопить значительные резервы, достигавшие 7 млн. номисм.