十五世纪末，以奥斯曼帝国为代表的东方穆斯林力量在经历了之前的十字军东征、蒙古入侵和内部分裂后，又进入复兴期。1517年奥斯曼帝国征服了埃及，并控制了地中海东岸的阿拉伯地区，随后在北非向马格里布进逼。与此同时，在欧洲狭小的伊比利亚半岛上，葡萄牙和西班牙崛起了，西班牙在排除伊比利亚半岛上的穆斯林势力的过程中完成了统一，并随之对外进行探险和扩张。尽管奥斯曼帝国这个时候很强盛，但以葡萄牙和西班牙为代表的欧洲基督教势力也处在复兴时期。崛起中的基督教西班牙王国和伊斯兰教奥斯曼帝国在西地中海遭遇，争夺对地中海航线和北非港口的控制权。
奥斯曼帝国在地中海地区的扩张威胁到了崛起中的西班牙，西班牙遂与埃及的马穆鲁克王朝结成暂时的联盟，以遏制奥斯曼土耳其人。同时，陷入基督教势力围攻中的格拉纳达穆斯林统治者也积极联络奥斯曼土耳其人，希望得到支援。但奥斯曼人因忙于跟马穆鲁克人的斗争而只能给予格拉纳达有限的支持，这也是格拉纳达于1492年陷落的原因之一。格拉纳达的陷落，标志着西班牙人最终完成了“再征服运动”，终结了在其南部地区长达近八百年的穆斯林统治。
随着“再征服运动”的完成，西班牙实现了统一，加上美洲的发现，为西班牙带来了巨额的财富，使西班牙成为欧洲强国并称霸世界。西班牙的贸易有两个方向，一个是向西，通往新大陆；另外一个是往东的传统地中海贸易。此时，奥斯曼帝国也在地中海进行扩张，他们的遭遇和冲突是不可避免的。
西班牙与北非的关系，既有新国家崛起与扩张的因素，也是“再征服运动”某种程度的延续。格拉纳达被征服后，那里的穆斯林面临着要么改宗基督教要么被驱逐的命运，新的基督教政权加在穆斯林身上的压迫是空前的，十五世纪末到十七世纪初，格拉纳达的穆斯林举行了多次反抗，但都被残酷地镇压下去，直到1609年，最后一个伊比利亚半岛上的穆斯林被送上了前往摩洛哥的船只。实际上，在长期的“再征服运动”过程中，大量的穆斯林被迫离开伊比利亚半岛前往北非定居，并在那里形成了对西班牙充满敌意的新社群。十六到十七世纪，来自伊比利亚的穆斯林难民得到了奥斯曼政府的帮助，得到了土地与安置，也有的在摩洛哥的大西洋沿岸占了地盘，沦为职业海盗，袭扰欧洲的船只与海岸村落，掠夺白人奴隶和战利品。
西班牙跟葡萄牙不同，它在非洲大陆没有直接的经济利益，西班牙对新世界的兴趣更大，包括力图在意大利建立其优势。但北非对西班牙造成的挑战使其不得不做出回应。1497－1505年间，北非的穆斯林对西班牙海岸发起多次猛烈攻击，并与格拉纳达的穆斯林起义形成了呼应，在地中海航行的西班牙船只更是经常遭遇穆斯林的攻击。为了应对这些挑战，西班牙在十六世纪初夺取了马格里布的很多港口，包括阿尔及尔与的黎波里。不过，西班牙人根本就没心思去确保对这些港口腹地的控制，这些港口的生存只能靠来自西班牙的供应，甚至包括食物。西班牙未能占领的地方则成为海盗的活动基地。
之后，奥斯曼土耳其人先后收复北非港口，并以这些港口为基地袭击欧洲的船只。在后来的竞争中，北非港口几经转手。土耳其人曾在十六世纪后期遭受两次大败，并因此失去了对地中海航线的掌控。但土耳其人保住了北非的主要港口基地，并从这里继续袭击基督徒的船只。这些北非港口背后的内地已经成为奥斯曼帝国正式的疆土，不过，伊斯坦布尔派驻的官员们主要还是居住在城镇里。这些地区内部的事务并没有被真正控制。
1516－1517年，奥斯曼人吞并了埃及的马穆鲁克，非常关注西班牙人最近在北非的活动。奥斯曼帝国与阿尔及尔的海盗建立了联系，并派出军队、战舰以及大量的现金支持海盗，借以袭扰西班牙人。海盗为奥斯曼政府卖命，阿尔及尔也成了奥斯曼帝国事实上的海军基地，迅速崛起为地中海上发达的港口城市。
十六世纪中叶，西班牙人不得不与奥斯曼帝国及其海盗联盟在北非抗衡。其间，突尼斯五次易手；西班牙还曾发动对阿尔及尔的大规模远征，但因为风暴而失败；海盗又夺取了西班牙控制下的的黎波里，这儿遂成为海盗袭击西西里和意大利的主要基地。奥斯曼帝国也有失利，比如远征马耳他失败。总之，西班牙人和奥斯曼及其盟友互有胜负。双方最终都认识到，再这样斗下去，彼此都得不偿失。1580年，他们签订了条约，承诺维持马格里布的现状。三年后，西班牙吞并了葡萄牙，并接管了葡萄牙在非洲的一些港口。但在接下来的几百年里，西班牙逐渐放弃了其绝大部分在北非的港口。
在十六世纪后期，除了摩洛哥外，马格里布的大部分变成了奥斯曼帝国的行省。尽管当地的政治动荡还在继续，但是，其版图在奥斯曼帝国的控制下维持了四百年的稳定。其间，的黎波里和阿尔及尔迅速发展壮大，奠定了北非现代国家的基础。
奥斯曼帝国对北非领地的松散控制对当地精英是有利的，他们继续纵容和支持穆斯林海盗与基督徒海盗之间的竞争，并从中受益，阿尔及尔的崛起在很大程度上就是得益于海盗带来的财富。海盗的活动影响范围极大，甚至也会袭击奥斯曼帝国的船只，更是给西方人造成了巨大的威胁，从十六世纪早期到十八世纪晚期，上百万欧洲白人被掳为奴，大量的物品被掠夺，以至于新生的美国海军也被迫卷入打击海盗的行动。（海盗在当时的世界并非罕见，荷兰、法国和西班牙王室也曾支持本国海盗。掳掠而来的人口被卖做奴隶更是司空见惯。还有一些自称穆斯林的海盗其实就是欧洲的亡命之徒，他们只是为了利益而暂时宣称皈依了伊斯兰教。）直到十八世纪，欧洲人才终止了北非海盗的活动。