Впервые мусульмане (возможно, приезжие торговцы), как выделяющаяся диаспора Сухума (в то время Себастополиса), упоминаются в документах начала XIV в. В частности, о них сообщается в жалобе католического миссионера Пиэтро Геральли (1330) на противодействие распространению западной ветви христианства со стороны местных жителей, в т. ч. и «сарацин» (т. е. мусульман).
В тот период времени в Египте у власти находится мамлюкская династия Бурджу, которую представляли «черкесы», т. е. абхазы, адыги, убыхи и частично грузины. Побывавший в 1779–1783 гг. в Тифлисе Я.Рейнегс писал об абхазах и черкесах: «В прежнее время многие из них отваживались отправляться в Египет, чтобы предаться там в солдаты или в рабство. В отряде мамлюков в самом Каире среди жителей было очень много таких, которые родились в горных долинах Абхазии». Многие мамлюки, заслужив высокие военные чины и положение в обществе, возвращаются на историческую родину, где строят первые мечети и становятся распространителями ислама. Эвлия Челеби повествует об одном из абхазских обществ: «Среди них есть абаза, приехавшие из Топхане. из Стамбула и из Египта. У них много мечетей и много мусульман с семьями и домочадцами». О следах того времени свидетельствуют и географические названия — находящийся возле г. Пицунда поселок носит название Мюссера (абхаз. Мсыр от арабск. Миср, т. е. Египет). По всей видимости здесь некогда находилось поселение абхазов-мамлюков, вернувшихся из Египта и назвавших свое место жительства по имени своей второй родины.
Основной период знакомства абхазов с исламом, османский, начинается после середины XV в., во времена правления султана Мехмеда II Фатиха, когда в 1462–1464 гг. султанат закрепляется в прибрежной части Абхазии. Тогда же в отстроенной заново турками крепости Сухум-Кале появляется официальный представитель султана. Уже в это время константинопольский патриарх Михаил констатирует: «Абхазия совсем отложилась от христианства». В XVI в. абхазские владетельные князья Абхазии официально признают власть первого халифа из рода Османов Селима I и становятся его вассалами, в 1578 г. флаг Абхазского княжества приобретает мусульманскую символику. О распространении ислама уже в тот период говорит найденная в Абхазии могильная плита ахуаджа ду Мехмеда, сына Насуха, которая датируется 1598 г.
Турецкий историк Кятиб Челеби (не ранее 1645 г.) так пишет о Сухуме: «…жители этого города мусульмане». Католический миссионер Кристофоро де Кастелли, побывавший в Грузии и Абхазии в то время, отметил: «…в 1650 году абхазский владетель со всей семьей являются больше мусульманами, чем иного вероисповедания». В том же веке в Сухуме строятся две большие деревянные мечети, что подтверждает в своей монографии «Новейшие географические и исторические известия о Кавказе» начала XIX в. С.М.Броневский, посвященной Кавказу: «В городе (Сухуме) и предместье заключается более тысячи домов…. две мечети и один фонтан». Это приводит и к тому, что в 1659 г. окончательно потерявший паству православный католикос Абхазии Захарий бежит из резиденции в Пицунде к себе на историческую родину в Грузию, в Гелати (как известно, все католикосы по национальности были грузинами). В 70-х гг. XVIII в. власть абхазских владетелей, носившая до того исключительно локальный характер, приобретает официальный статус в османском государстве. Владетель Леван (Мухаммадбей) Чачба становится первым пашой Абхазии, получив при этом во владение крепость Сухум-кале. Турецкий гарнизон при этом покидает Абхазию, а войска владетеля уже считаются османскими.