拜占庭帝国与阿拉伯人的关系始于4世纪。古阿拉伯人原为阿拉伯半岛的闪米特游牧民族，在其兴起以前，拜占庭人即通过商业贸易与古代阿拉伯人发生接触。4世纪时，拜占庭帝国驻防红海和幼发拉底河的边防部队就与阿拉伯人的塔努基德斯小王朝发生摩擦。5世纪，波斯人控制下的拉赫姆王国（Lakhmids）经常发动对拜占庭帝国边境城乡的洗劫。6世纪，阿拉伯人加沙尼德斯小王朝（Ghassanids）与拜占庭人关系友好，其王公贵族在帝国军队和政府中任职。632年，穆罕默德创立政教合一的伊斯兰国家，统一了阿拉伯半岛，其继承者哈里发对外发动大规模侵略扩张战争，遂与拜占庭帝国发生严重的军事冲突。636年，阿拉伯军队在雅穆克河战役（Battle of Yarmouk）击败拜占庭军队，取得了决定性胜利。此后，阿拉伯军队以不可阻挡之势，横扫西亚、小亚细亚和北非的拜占庭领土。其北路军在数十年内清除了巴勒斯坦、叙利亚和小亚细亚大部分地区的拜占庭势力，其西路军夺取拜占庭帝国在埃及和马格里布的全部领地，而后渡过直布罗陀海峡占领了西班牙大部。其海军则逐渐控制了东地中海和爱琴海航路，兵临君士坦丁堡城下。649年，阿拉伯海军侵入克里特，5年后夺取罗得岛，封锁了拜占庭帝国对外联系的海上通道。670年，阿拉伯人在君士坦丁堡南面马尔马拉海建立基兹科斯（Cyzicus）海军基地，开始对拜占庭首都发动围攻。

当时，阿拉伯帝国在军事扩张中取得了巨大胜利，占领了亚洲和非洲广大土地，几乎将拜占庭人驱逐出其亚洲和非洲领地。673—677年，阿拉伯海军以马尔马拉海东部的基兹科斯港为海军基地，对君士坦丁堡发动了连续多年的进攻。678年的夏季，哈里发穆阿威叶调集大批船只，发动了更大规模的攻势，以数百艘战舰对君士坦丁堡猛攻。拜占庭海军则利用“希腊火”，将阿拉伯海军的木船烧毁。在退却中，阿拉伯海军又遭到暴风雨的袭击，拜占庭舰队则乘机反攻，将剩余的阿拉伯船只消灭在奇里乞亚海港城市西莱夫基亚附近，使阿拉伯海军几乎全军毁灭。这次失败迫使阿拉伯要求和谈。同年，拜占庭和阿拉伯双方订立30年和约，哈里发穆阿威叶表示降服，愿意每年向拜占庭帝国进贡；两国都承诺在30年内互不侵犯，维持目前的边界。该和约在东欧产生了强烈的反响，阿瓦尔人汗王和斯拉夫人各部落首领纷纷前往君士坦丁堡请求和平和友谊，承认拜占庭帝国的宗主权。该和约还标志阿拉伯军事扩张的势头被最终阻遏，阿拉伯人征服欧洲的计划也因此最终破产。阿拉伯人曾于669年、674—680年和717年三度包围拜占庭首都，但是都遭到了失败。718年，拜占庭皇帝利奥与阿拉伯帝国倭马亚王朝哈里发奥马尔（Omar）订立7年和约，规定在此期间互不侵犯，允许各自的商人从事贸易，并保证信徒信仰自由；阿拉伯人允诺许可基督徒前往耶路撒冷圣地朝圣。这一和约得到双方认真的履行，两国间维持了14年的和平。750年，阿拔斯王朝取代倭马亚王朝统治后，拜占庭和阿拉伯两国关系进入新时期。

8世纪末，阿拉伯人再度挑起两国争端。780年，拜占庭皇帝利奥四世去世，由10岁的君士坦丁六世即位，皇后伊琳娜摄政。782年，阿拉伯军队乘拜占庭军队主力西调西西里平息叛乱之机起兵入侵，兵临君士坦丁堡城下。伊琳娜鉴于后方空虚，立即提议无条件和谈，订立3年和约，承认双方既定领土，缴纳重金年贡。这一和约虽然暂时阻止了阿拉伯军队的进攻，但是拜占庭帝国因此丧失了前代历任皇帝取得的胜利成果。797年，伊琳娜勾结禁卫军发动宫廷政变，废黜了其子君士坦丁六世。次年，阿拉伯军队又乘拜占庭皇室内乱之机入侵，袭击君士坦丁堡郊区和博斯普鲁斯海峡地区，迫使伊琳娜女皇于781年再次主动提议媾和，派遣使节与哈里发和谈，订立了和约，保证继续向哈里发缴纳年贡，并再次承认阿拉伯人对小亚细亚的占领和对该地区的移民。伊琳娜女皇的乞和行为对拜占庭帝国在亚洲地区的权益产生了极为深远的恶劣影响。

9世纪前半期，阿拉伯人对拜占庭帝国的进攻没能取得实质进展，因此，两国除了在小亚细亚边境地区时有小规模冲突外，没有发生大规模战争。而两国的文化、经济和商业往来迅速增加。10世纪以后，随着阿拔斯王朝中央集权的衰落，拜占庭帝国与阿拉伯人各地政权的关系更为密切。在西地中海，以突尼斯为中心的阿弗拉比王朝进攻并占领了西西里，以叙利亚阿勒颇（Aleppo）为中心的阿拉伯军队与拜占庭人争夺小亚细亚东部地区，马其顿王朝的皇帝将拜占庭帝国东部疆界推进到幼发拉底河和巴勒斯坦地区。十字军战争期间，拜占庭和阿拉伯两国没有发生直接冲突，而是分别坐视西欧骑士与突厥人交战。

10世纪中期，随着阿拉伯帝国的解体，拜占庭帝国注意发展与各地穆斯林政权的关系。当时，马其顿王朝统治下的拜占庭帝国国势鼎盛，计划发动对东地中海阿拉伯海盗的清剿，故首先派出夺取克里特岛的远征军。在进行大规模军事行动之前，拜占庭人开展积极的外交活动，争取地中海各阿拉伯伊斯兰教政权的中立，特别注意与西班牙阿拉伯人建立友好关系。947年和949年，拜占庭皇帝君士坦丁七世两度遣使科尔多瓦（Cordoba），向哈里发阿卜杜－拉赫曼三世（Abd-ar-Rahman III）进献礼物，其中包括哈里发特别喜好的古代希腊手稿和精美的拜占庭宝石项链、念珠。拜占庭帝国积极的外交姿态促使哈里发决心与拜占庭人订立友好条约，在条约中，哈里发保证在即将发生的战争中保持中立。该条约孤立了克里特的阿拉伯海盗，保证了拜占庭帝国在海战中的有利地位。

与此同时，拜占庭帝国积极发展与法蒂玛王朝的友好关系。法蒂玛王朝是以伊斯兰教先知穆罕默德的女儿法蒂玛（Fatima）之名命名的，它于909—1171年统治埃及和北非。该王朝建立后，积极进行军事扩张，911年，在西西里与拜占庭军队发生第一次冲突。为了阻止法蒂玛王朝军队的进攻，拜占庭帝国驻西西里总督于914—918年同意向法蒂玛王朝提供22000金币的年贡，但是这笔年贡到罗曼努斯一世时被减少了一半。946—958年间，两国经过和平谈判达成3次停战协议，967—975年间，双方订立过两项和解条约。上述外交协议大多限于西西里地区的双边关系，而在叙利亚地区法蒂玛王朝则进行大规模扩张。10世纪，拜占庭海军击败法蒂玛王朝舰队，夺取克里特岛。987年，哈里发阿齐兹在谈判中说服拜占庭人取消对法蒂玛王朝商人的贸易限制，允许法蒂玛人在君士坦丁堡的清真寺内为哈里发祈祷。当时的法蒂玛王朝以伊斯兰教世界的主宰和保护人自居，哈里发阿齐兹临终前已经计划远征拜占庭人，以保护小亚细亚的罕达尼埃米尔国（Hamdanid dynasty）。998年，法蒂玛王朝舰队终于击败拜占庭海军，迫使后者于1001年订立屈辱的10年和约。1015—1032年，控制了整个西亚地区的法蒂玛王朝迫害基督教徒，两国的商业关系因此受到严重影响。拜占庭帝国马其顿王朝皇帝因此发动对阿拉伯人的远征，收复了小亚细亚和叙利亚的一些失地。1038年，双方订立10年和约，法蒂玛王朝被迫允许拜占庭人修复其在耶路撒冷等城市的教堂，允诺停止迫害基督教徒。1048年，和约到期后，双方重新续订和约。此后，由于塞尔柱人的兴起和扩张，法蒂玛王朝和拜占庭帝国两国关系得到改善。塞尔柱人对西亚地区的占领，以及由此引发的西欧十字军东征使拜占庭人与法蒂玛王朝的领土联系中断，但是两国的外交往来一直保持到1171年法蒂玛王朝灭亡。

11世纪以后，随着阿拉伯世界的分裂和拜占庭帝国的衰落，地中海政治版图和国际关系格局发生了根本变化，两国基本上停止了往来，而伊斯兰教化的土耳其人取代了阿拉伯人的地位。