Рядом с его столпом близ южной гавани Митилины возник монастырь Пресвятой Богородицы. Во время иконоборческих гонений Симеон основал на маленьком островке в заливе Ера церковь мученика Исидора. Местное предание связывает с Лесбосом деятельность одного из главных защитников иконопочитания – преподобного Феофана Сигрианского. В IX–XI вв. Лесбос был местом ссылки государственных и церковных деятелей (императрица Ирина Афинянка, Константинопольский патриарх Игнатий, преподобный Николай Студит, будущий император Константин IX Мономах и др.). Местные легенды связали с именем императрицы Ирины, которая умерла на Лесбосе в 803 г., основание ряда монастырей: Рождества Пресвятой Богородицы на Карийском холме близ Терми (Лутрополи-Термис), Пресвятой Богородицы Труллоти в селении Пирьи-Термис, апостола Иоанна Богослова (Ипсилу), который, по другой версии, основан сирийским монахом в VII в. В начале Х в. (согласно Дж. Федальто, между 850 и 900 гг.) Митилинская архиепископия была возведена в ранг митрополии, а в её пределах были образованы подчинённые ей епископии (Эресская или Эрисская, Стронгильская, Тенедосская, Вервинская, Перперинская; в 1261 г. впервые упоминается Иерская епископия). Мифимнская архиепископия стала митрополией в XII в. (по Дж. Федальто, около 1080 г., по Й. Кодеру, в 1084 г. или между 1072 и 1082 гг.). В средневизантийский период Лесбос был частью фемы Эгейского моря. Здесь родился византийский поэт XI в. Христофор Митилинский (около 1000 – после 1054 гг.). Около 1088 – 1091 гг. эмир Чаха захватил Митилину, но не смог взять Мифимну (Моливос). В 1092 г. Иоанн Дука освободил Лесбос. В XII в. остров несколько раз был разграблен венецианцами. Епископ Асса Эфесского Григорий (XI или XII в.), основал монастырь Пресвятой Богородицы на горе Приант близ залива Ера и провёл в нём последние годы жизни. После захвата Константинополя крестоносцами (1204 г.) Лесбос перешёл во владение императора Балдуина I Фландрского. В 1224 г. остров был отвоёван никейским императором Иоанном III Дукой Ватацем. В 1235 г., во время пиратского набега на монастырь Рождества Пресвятой Богородицы на Карийском холме, приняли мученическую смерть преподобномученицы Олимпия и Евфросиния (память в Греческой церкви 11 мая). В 1355–1462 гг. на Лесбосе правил генуэзский род Гаттилузи, т.к. византийский император Иоанн V Палеолог отдал этот остров Франческо Гаттилузио в качестве приданого своей сестры Марии. В тот период были основаны две латинские епископские кафедры – в Митилине и в Мифимне, монахи-доминиканцы вели прозелитическую деятельность. В 1438–1439 гг. Митилинский митрополит Дорофей принимал участие в Ферраро-Флорентийском соборе. В 1462 г. Лесбос захватили турки. Местные жители оказывали сопротивление, что вызвало репрессии со стороны завоевателей. В 1463 г., во время карательной операции, были убиты преподобномученики Рафаил, Николай и мученица Ирина. Первое время после османского завоевания остров пришёл в запустение, в том числе монастыри, на нём расположенные. Когда в 1520 гг. преподобный Игнатий Агаллиан, митрополит Мифимнский, начал восстановление Лимоноса и монастыря Пресвятой Богородицы Мирсиниотиссы, по свидетельству его сына игумена Мефодия («Завещание», 1576 г.), на Лесбосе не было ни одной обители и ни одного монаха. После 1462 г. и до 1526 г. кафедра Мифимнской митрополии была перенесена в Калони. После поражения турецкого флота в битве при Лепанто (1571 г.) на ряде островов Эгейского моря прошли антитурецкие выступления, в наказание за это на Лесбосе турки убили неизвестного по имени Митилинского митрополита и четырёх священников.