Oruç Reis’den sonra Cezayir Sultan’ı olan Barbaros Hayreddin Paşa Kuzey Afrika topraklarında Cihan Hakanı’ndan başkası adına hutbe okutulup sikke basılmasına karşı duyduğu rahatsızlığı Afrika’daki çeşitli Arap Emirlerini kabul ederek kendilerine anlattı. Bunun üzerine Cezayir’deki Kadı Alimler İmamlar Hatipler Tüccarlar Eminler ve bütün Re’ayâ tarafından hazırlanan mektup Hacı Hüseyin Ağa liderliğindeki bir heyetle İstanbul’a gönderildi ve Cezayir’in Osmanlı Devleti’ne bağlanma isteği bildirildi:
“Cezayir’deki Kadı Alimler İmamlar Hatipler Tüccarlar Eminler ve bütün re’ayânın Sultan’a mektubudur.
Sultanımızın yüce makamına zafer ve saadet dualarımızı takdim ettikten sonra Cezayir’de olan biz bendeleri size yazıp i’lan ediyoruz ki:
Sizin bizim yanımızda büyük bir mertebeniz vardır. Gün geçtikçe size ta’zimin vücubuna ve lüzumuna daha çok inanıyoruz. Biz tazimlerimizi size arzetmek istiyoruz ki mektup onun ifadesine kâfi değildir. Biz saadetinizle sevinçliyiz. Size öyle itimat ediyoruz ki güvenimizin içi dışı evveli ve ahiri güzel olacağınıza inanıyoruz. Emrinize hazırız. Bu bendelerinizin size hürmetten başka şeyleri yoktur. Şerefli makamınızın devamını istiyoruz. Bu bendelerinizin Allah düşmanlarının yaptıkları zulümler ve Allah dostu olan mü’minlerin yardımları ile ilgili haberleri uzundur. Ancak özeti şudur ki:
Azgın kafirler Endülüs’ü istila ettikten sonra Vehrân kalesine geldiler. Diğer müslüman beldelere tecavüz için Becaye ile Trablus’u aldılar. Sadece bizim diyarımız olan Cezayir kaldı. Daire ortasında kalan nokta gibi garip ve şaşkın kaldık. Her taraftan kâfirler bizi sıkıştırdı. Biz de Habl-i Metin olan dinimize sarılıp Allah’a sığındık. Kâfirler bizi hakimiyetleri altına almak istediler. Biz de baktık gördük ki başka çâremiz yok.

Ehl-i teslise mal çoluk-çocuk perişan olmasın diye itaat ettik. Bu sıkıntıdan sonra kâfirler geldi; Vehran’ı Becâye’yi ve Trablus’u aldı. Gemilerle bizi esir almaya uğraştılar. İşte bu sırada büyük mücahit Oruç Bey bir miktar gazilerle çıkageldiler. Biz de onu karşıladık. Ve “Allah’ın fazlıdır” dedik. Bizi kurtardı. Daha önce Becaya kalesine gelmiş orayı almış ve mücahit Fakih Ebül-Abbas Ahmed bin Kadı ile kurtarmışdı. Kâfirlerin bir kısmı kaçtı ve bir kısmı da öldürüldü. Müslümanlar galip oldular. Sonra Oruç Bey oradan ayrılıp bizim imdadımıza koşmuştu. Oruç Bey Telmesan savaşında şehid olunca kardeşi mücahit Hayreddin ona hayr’ul halef oldu. Tam adaleti ve Şer-i Şerife ittibaından başka bir şeyi görmedik. Bize hâmi oldu. Mezkur size de çok ta’zim etmekte cihadı asıl vazife bilmekte ve her şeyini Allah yolunda feda etmektedir. Kendisini ilâyi kelimetullah’a adamıştır. Bütün gayesi size hürmet ve itaat olduğundan biz de onu sevdik. Nasıl sevmeyelim ki bizimle birlikte cihad için at koşturmaktadır.

Bu sebeple yüce makamınıza arzumuz şudur ki; Emirimiz Hayreddin size dönmek istiyordu. Buranın ileri gelenleri bırakmadılar; “Hristiyanlardan korkarız” dediler. Bu sebeple size elçimiz olarak Fakih Ebül-Abbas Ahmed gönderildi. Biz emirimizle beraber sizin hizmetinizdeyiz. Diğer hususları mektubu getiren size arzedecektir. 1-10 Zilkade 925 (Ekim 1519)” Yalı Köşkü’nde Yavuz Sultan Selim tarafından kabul edilen ve mektubu Sultan’a sunan heyet İstanbul’da 41 gün kaldı. Teklifi memnuniyetle kabul eden Yavuz Sultan Selim Barbaros’u Cezayir Beylerbeyliği’ne atadığını belirten Ferman-ı Hümayun’u verdi. (1519) Ayrıca Barbaros’a gönderilmek üzere mücevherli bir kılıç sırmalı bir hil’at ile “Beylerbeylik Sancağı” Hacı Hüseyin Ağa’ya teslim edildi.
Heyet Cezayir’e müjdeli haberleri getirince merasim düzenlenerek Barbaros’a kılıç kuşatılıp hil’at giydirildi. Sancaklar çekilip gece büyük bir ziyafet verilerek eğlenceler tertip edildi. Artık bir Osmanlı toprağı olan Cezayir’de “sikkeler” Osmanlı Padişahı adına basılmaya “hutbeler” Osmanlı Padişah’ı adına okutulmaya başlandı.