Арабская экспансия в Средиземноморье стала другой долговременной угрозой для христианских государств. Мусульмане в Западном Средиземноморье действовали главным образом из Северной Африки и изначально стремились к территориальным захватам. Завоевание Сицилии, принадлежавшей Византии, начавшееся в 827 г., как всегда бывало в истории этого острова, растянулась на десятилетия. Последний оплот византийцев Таормина пал в 902 г. Мусульмане смогли на время закрепиться в Калабрии и Апулии: в Таранто с 840 по 880 г. и Бари с 841 по 871 г. Но продвижение в Италию в конечном счете успеха не имело.
Тем не менее грабительские набеги арабов существенно повлияли на социальную и политическую жизнь региона. В 846 г. мусульмане разграбили собор Св. Петра в Риме, вынудив папу Льва IV около 850 г. обнести Ватикан крепостной стеной. Современные историки сопоставляют с волной разбойничьих набегов процесс перехода к укрепленным деревенским поселениям сеньориальной эпохи. Этот процесс понимается ими как ключ к развитию сеньориальной власти и переустройству средневекового общества в целом. Причем это суждение впервые звучит из уст средневековых хронистов. К концу IX в. те относят последние свидетельства об идиллическом счастье, царившем некогда в Средней Италии. Деревень тогда почти не было, преобладали хутора и обособленные усадьбы, где каждая крестьянская семья была предоставлена сама себе. Но наступила великая смута, превратившая крестьян в деревенских жителей. Полагая спастись от сарацин, они оказались заперты в новых укрепленных деревнях, где роковым образом потеряли былую независимость и попали под гнет сеньоров.
На Сицилии и в Испании первые отряды мусульман высадились по приглашению христиан для войны с другими христианами. В начале VIII в. Вестготское королевство включало почти всю Испанию и часть Южной Галлии. По свидетельству мусульманских источников, просьба о военной помощи исходила от сыновей только что умершего вестготского короля Вити-цы, считавших себя неправильно отстраненными от власти. Первым в 711 г. высадился отряд правителя Танжера Тарика, но его составляли не арабы, а берберы. Вестготы были разбиты, а их король пал в бою или был убит вскоре после этого. На следующий год в Испанию переправилась армия мусульманского правителя Северной Африки Мусы, включавшая теперь большое число арабов. Покорение страны произошло стремительно и в основном завершилось к 716 г. Мусульманская экспансия продолжилась за Пиренеями, пока не встретила отпор и затем ответное наступление со стороны франков. Концом мусульманского продвижения в Европу считается победа Карла Мартелла, одержанная им в 732 г. в битве при Пуатье. Впрочем, историки оговариваются, что это могла быть небольшая грабительская экспедиция, организованная, возможно, не без помощи христианских правителей Аквитании.
Пришедшие в Испанию арабы принадлежали не к бедуинам, а в основном происходили из земледельческих регионов Йемена. Арабы селились в крупных городах и долинах рек Гвадалквивир и Эбро. Берберы занимали плоскогорья в центральной части страны, пригодные для скотоводства. Мусульманская Испания сразу оказалась во власти бесконечных внутренних раздоров между берберами и арабами, между арабами йеменских племен и новыми волнами арабских переселений, в основном из Сирии, которые принесли в новую страну старые распри, возникшие еще в Аравии. Когда между 747-750 гг. Аббасидам удалось отстранить от власти багдадских халифов из рода Омейядов, один из Омейядов Абд ар-Рахман I (756-788) сумел основать независимое государство в Испании, приняв титул эмира. В условиях неустранимых племенных раздоров опорой государственной власти стали мулади («новые мусульмане»), т.е. обратившиеся в ислам неарабы. Та часть правящего класса Вестготского королевства, которая осталась на завоеванных территориях, быстро влились в состав новой элиты. Перенимавших арабский язык и обычаи, но не менявших веру называли мосарабами. Мирному включению жителей Испании в состав нового государства способствовала терпимость его правителей к христианству.
Немусульмане платили особый налог, а когда во второй половине IX в. началось массовое обращение в ислам, государство осталось без средств, что нанесло разрушительный удар по эмирату Омейядов. Кордовские эмиры изначально контролировали юг страны. К середине IX в. Абдарахман II (822 852) смог подчинить мусульманские пограничные «марки» на севере и в центре Испании, но всего на несколько лет, после чего власть кордовских эмиров впредь ограничилась долиной Гвадалквивира и ближайшими окрестностями Кордовы. Однако уже в X в. при Абдарахмане III это государство станет сильнейшим в Европе.