Najraniji historijski zabilježeni kontakt između balkanskih Slavena i islama dogodio se u vrijeme prodora mješovite vojske sastavljene od Bugara i Arapa, te pripadnika različitih turskih plemena koja se kretala iz Središnje Azije pod zapovjedništvom Asperuh-hana (644-701). Oni su rijeku Dunav prešli i stupili na bugarsko tlo godine 680. To je i historijski trenutak početka opadanja moći Bizantskog imperija usljed učestalih napada Avara, Arapa, Perzijanaca, Slavena, Bugara i drugih etničkih i plemenskih skupina uglavnom turskog porijekla.
Dunavski Bugari, pod zapovjedništvom Asperuh-hana, napadali su bizantske zemlje s kopna, dok su se Arapi koncentrirali na napade na Konstantinopol s mora. Velika skupina Slavena služila je i u balkanskim avarskim snagama, uglavnom kao pješaštvo, ali i kao posade osobitih brodova zvanih monoksil (čamaca načinjenih od izdubljenog debla) kojima su perzijske trupe prelazile Bosfor s azijske na evropsku stranu.
Kažu da su Slaveni bili iznimno cijenjeni zbog svoje vještine u izradi i upravljanju ovim brodovima te su ih različite etničke skupine koristile kao najamnike za prelazak rijeke Dunav, kao i u vrijeme napada na Konstantinopol iz 626. Dolazak Arapa i Perzijanaca na područja jugoistočnog Balkana značajno je stoga što su oni prvi muslimani koje su balkanski narodi upoznali. Na sjeveru bizantskog teritorija, odnosno na kopnu Balkanskog poluotoka, već su živjela mnogobrojna slavenska plemena i plemenske zajednice, među kojima su bili i neki koji su tu živjeli već generacijama.
Prvi kontakti između Arapa i bosanskih Slavena najvjerovatnije su rezultat dolaska arapskih istraživača i avanturista, te njihovih pomorskih napada na obale Balkanskog poluotoka. U to vrijeme pojavljuju se i prva, istina malobrojna, muslimanska naselja, što bilježe srednjovjekovni evropski arapski izvori. Historičari tvrde da su muslimanski misionari i trgovci u ranom srednjem vijeku posjećivali muslimanska naselja na Balkanu.
Poznato je da su neki od balkanskih muslimana bili vješti moreplovci čije vještina i prisustvo na Jadranskom moru nisu mogli proći nezapaženo; arapski geograf al-Idrizi u vrijeme svoje posjete zemljama Balkanskog poluotoka (1151–1159) ističe da su njegovi stanovnici sposobni i vješti moreplovci. Isto tako, Toma Arhiđakon (1200–1260) piše da su Slaveni koji su živjeli uz obalu Jadranskog mora stupili u kontakt s Arapima tokom njihovog napada i prodora duž istočne Jadranske obale. Arapski putopisac Ja’kut al-Hamevi u svom djelu Mu’džem bilježi da u ovom dijelu svijeta Slaveni i muslimani žive jedni pored drugih. Također, historijski izvori navode da je lokalni muslimanski vladar Domald Saracen bio “zaštitnik patarena” ili bosanskih bogumila.
