Oruç Reis, Pulya sahillerinde iki Venedik gemisini içindeki 24.000 altın, mal ve erzakla birlikte ele geçirdi. Daha sonra Eğriboz yakınlarında üç Venedik gemisiyle savaşarak 285 esir ve pek çok ganimet alıp Midilli'ye kardeşlerini ziyarete gitti. Elde ettiği ganimetleri memleketindeki akrabalarına ve yoksullara dağıttı. Tekrar Şehzade Korkut'u ziyaret etmek istediyse de I. Selim'in padişah olduğunu ve Korkut'un takibata uğradığını öğrendi. Bunun üzerine kış mevsimini geçirmek için İskenderiye'ye gitti, Memlük Sultanı Kansu Gavri'ye sığındı ve ondan iltifat gördü. O kışı sefer hazırlıkları ile geçiren Oruç Reis beraberindeki Yahyâ Reis ile birlikte ilkbaharda denize açıldı.
Kıbrıs yakınlarında beş Venedik ticaret gemisini zaptederek Cerbe adasına yöneldi ve gemileri tüccarlara satıp Mısır sultanına kıymetli hediyeler gönderdi. Cerbe'yi kendisine merkez yaptı, akın faaliyetlerini buradan yürüttü. Bu sırada kardeşi Hızır Reis de (Barbaros Hayreddin) ona katıldı. Anadolu'daki taht kargaşası yüzünden iki kardeş Tunus'a gitti. Tunus Sultanı V. Muhammed ile görüşerek ondan kendilerine bir yer göstermesini istediler ve elde edecekleri ganimetin beşte birini vermeyi teklif ettiler. V. Muhammed onları Halkulvâdî Kalesi'ne yerleştirdi.