Первая война между турками и венецианцами тянулась пятнадцать лет и завершилась уступкой туркам Негропона (древняя Эвбея), а также некоторых торговых поселений в Морее. Венецианцы также согласились ежегодно платить туркам дань за торговые права на Востоке. В этот период войны с сильным морским государством турки начали расширять свой военно-морской флот и всерьез заинтересовались Эгейским морем и его островами. На древнем архипелаге турки начали осваивать искусство мореплавания, так же как это делали до них греки много веков назад. Отсюда они в конце концов распространились по всему Средиземному морю, не пропуская ни одного порта. Одно время даже папа опасался, что может проснуться утром и увидеть на улицах Рима турецких мародеров.
Острову Лесбос судьба предназначила важную роль (пусть даже косвенную) в турецкой военно-морской экспансии. Здесь Якуб, один из янычар султана, женился на вдове греческого священнослужителя, которая родила ему шестерых детей, двух дочек и четырех сыновей, двое из которых, Арудж и Хизр, были ответственны за распространение турецкой власти в Средиземноморье. Один заложил фундамент королевства Алжир, а второй стал адмиралом османского флота.
Их карьера началась – как и карьера многих островитян того времени – с плавания на маленьких прибрежных судах.
Побочным заработком стало пиратство. Султан не возражал, если его людям нравилось нападать на торговое судоходство венецианских и генуэзских островов, – напротив, это его устраивало. Аруджу, старшему из братьев, не повезло столкнуться в одном из своих плаваний с большой галерой, принадлежавшей ордену рыцарей-иоаннитов, который, обосновавшись на Родосе, продолжал войну с мусульманами. Он попал в плен и стал рабом на галере, но позже его выкупили, вероятно, во время обмена пленными, которые время от времени имели место. Тяжелый опыт не сломил его дух, скорее наоборот, он стал ненавидеть христиан еще сильнее. За несколько следующих лет Арудж и Хизр приобрели репутацию хороших мореходов и безжалостных пиратов. Они действовали между занятыми латинянами Эгейскими островами. В период между 1500 и 1504 годами оба брата направились на двух галерах в Северную Африку. Они договорились с правителем Туниса, что будут действовать из его порта, в обмен на часть денег, добычи и рабов, которую сумеют захватить, нападая на христианские суда.
Ситуация в Северной Африке, где сохранилось невообразимое смешение султанатов и эмиратов, образовавшихся во времена арабских завоеваний, благоприятствовала действиям турок. В 1492 году после покорения Гранады – последнего уцелевшего мусульманского государства на испанском полуострове – суверены Испании добились победы, которая повсеместно превозносилась как триумф христианского оружия. Однако не обошлось без последствий, которые еще несколько веков тревожили Западное Средиземноморье.
Стэнли Лейн-Пул в книге «Корсары южных морей» писал: «Когда объединенной мудростью Фердинанда и Изабеллы было принято решение об экспатриации испанских мавров, правители позабыли о риске мести изгнанников. После падения Гранады тысячи испанских мавров покинули землю, на протяжении семи веков бывшую их домом, и, не желая жить под испанским игом, переправились в Африку, где обосновались в разных местах – Шершеле, Оране, Алжире, о которых раньше не слышали. Не успели изгнанные мавры осесть на новом месте, как начали то, что сделал бы любой на их месте, – начали войну против страны угнетателей».
До прибытия мавров в Северную Африку отношения между разными мусульманскими государствами побережья и европейцами оставались нормальными и деловыми. Заключались соглашения, условия которых уважались обеими сторонами. Между Испанией, Францией, итальянскими государствами и мусульманским миром велась активная торговля. Все это изменилось с появлением на этих берегах озлобленных мавров, жаждавших мести и, если возможно, возвращения домой в Гранаду. В то же самое время экспансия турецкой силы в восточной части моря подталкивала молодых энергичных турок, таких как Арудж и Хизр, к поиску счастья в Африке. Они использовали чувства мусульман в Северной Африке и превратили весь центральный и западный бассейн в поле боя. В это время возникло географическое название, вселявшее страх в сердца европейских купцов, морских капитанов, жителей побережья, рыбаков и даже принцев – Варварский берег.
В те годы, когда два брата-турка расширяли свою власть и влияние вдоль побережья от Туниса до Алжира, их нападения на европейское судоходство не могли остаться незамеченными. В 1504 году они добились первого и самого примечательного успеха, захватив на двух маленьких турецких галеотах две большие итальянские галеры, одна из которых была папским флагманом – одним из самых крупных судов, действовавших тогда на Средиземном море. Но это было только начало. Вскоре, прибегнув к помощи других турок, маврских экспатриантов из Гранады и христианских ренегатов, они превратили некогда спокойное североафриканское побережье в самую серьезную угрозу торговле (после вандалов) в этой части моря.