Их первоначальным снаряжением была легкая галера, экипаж которой составляли около 100 добровольцев, жаждавших добычи и славы. Примерно в 1502 году их базой стала Джерба, издавна служившая гнездом пиратов и местом столкновений между христианскими захватчиками и мусульманскими защитниками. Они наладили связи со двором в Тунисе, действуя как лицензированные пираты султана Хафсида; в 1504 году они отправились на Эльбу, чьи глубокие бухты благоприятствовали корсарам, и набросились на две галеры, которые, как оказалось, шли на службу к папе Юлию II, а также на испанский корабль, перевозивший 300 солдат и шестьдесят арагонских дворян в Неаполь. Они легко захватили галеры, значительно укрепив свою репутацию героев в Тунисе и страшных врагов в Риме. К 1506 году у них было восемь кораблей, а их успехи принесли им такую славу, что османский султан присвоил им почетный титул "защитника веры", хайр-ад-дин, или, по-турецки, "хайреттин". Война на истощение велась между мусульманскими корсарами и их христианскими противниками; это были не только генуэзские и каталонские моряки (купцы или корсары), но и португальцы и испанцы, которые настойчиво вторгались в прибрежные крепости на средиземноморском и атлантическом побережьях Марокко. Несмотря на успехи в Мелилье и Оране, лучшее, чего испанцы смогли добиться в Алжире, - это захват нескольких изолированных скал, охраняющих порт, которые в 1510 году были укреплены пушками, но это не заменило контроля над городом.12
Во время этих конфликтов у мусульман было одно большое преимущество: они могли заручиться поддержкой вождей-воинов в марокканской глубинке вокруг Тетуана. Лето они проводили на море, совершая набеги на Испанию и уводя с собой тысячи рабов, которых они использовали для строительства оборонительных сооружений Тетуана. Хизр утверждал, что за один месяц захватил двадцать одно торговое судно и 3800 христианских рабов (включая женщин и детей). Братья неустанно совершали набеги на Майорку, Менорку, Сардинию и Сицилию, и о влиянии их набегов можно судить по количеству городов и деревень, которые отошли от опасного побережья западных островов Средиземного моря и были отстроены на несколько миль вглубь страны.13 Урудж приобрел репутацию кровожадного человека, способного выкусить жертве дыхательное горло, как бешеный мастиф, но он был проницательным политиком и использовал свою репутацию для достижения политических целей. Он создал собственное королевство, начав с города Джиджелли на алжирском побережье. Его жители были впечатлены, когда он захватил сицилийскую галеру, груженную пшеницей, в то время как их собственные запасы были очень скудными. Они предложили ему возглавить страну, и вскоре он совершил переворот в Алжире. Он воспользовался кризисом престолонаследия в Тлемсене, важном городе, расположенном немного в стороне от моря, и в 1517 году сделал себя его хозяином. Все это сильно беспокоило испанцев, базировавшихся в Оране, которые пытались наладить дружеские связи с местными вождями.14 Новый правитель Испании, Карл Габсбургский, понимал необходимость мобилизации войск в своих североафриканских владениях. К счастью, проблема Тлемсена была решена жителями, которые увидели в Урудже агента турецкого владычества; прогнав его, он попал в ловушку испанских войск и был убит в бою.
Второй Барбаросса, Хизр, более известный как Хайреттин, теперь приобрел еще более грозную репутацию, чем Урудж. Чтобы подчеркнуть свою преемственность по отношению к старшему, рыжебородому Барбароссе, он покрасил свою собственную бороду в рыжий цвет. Он укрепил свои позиции в прибрежных городах Магриба, сумев в 1529 году отбить у испанцев крепости на островах у входа в Алжир15 .15 В том же году он разгромил испанскую флотилию у острова Форментера на Балеарских островах, до которых теперь было рукой подать, и захватил семь галер вместе с их капитанами; когда он стал раздражаться на капитанов, то приказал изрубить их острыми ножами.16 Алжир стал столицей Барбароссы, но он позаботился о том, чтобы найти защиту у османского султана. Он находился достаточно далеко от Константинополя, чтобы сохранять автономию, и был достаточно ценен для османского султана, чтобы пользоваться материальной поддержкой Возвышенной Порты. Османские султаны переключали свое внимание со Средиземноморья на Балканы и Персию, и борьба с сефевидскими шахами на Востоке часто отвлекала их от средиземноморских дел. Поэтому было разумно действовать через агентуру Хайреттина Барбароссы, а не направлять все свои ресурсы на один из этих театров военных действий. Барбаросса получил официальное признание в качестве эмира Алжира и любил называть себя капудан-пашой, "генерал-капитаном". Султан Селим I прислал ему турецкий штандарт, пушки и военное снаряжение, а также 2 000 янычар.