خير الدين بربروس استمر عروج بعد أن نال حريته في العمل في البحر الأبيض المتوسط وذهب إلى الإسكندرية واستقر مدة فيها، وعندما كان هناك استدعاه السلطان المملوكي قنصوه الغوري للمثول بين يديه، وكلفه بقيادة أسطوله، فوافق عروج على ذلك، وذهب إلى ميناء بياس بخليج الإسكندرون لجلب الأخشاب الكافية لصناعة الأسطول على أن يتجه بعد ذلك إلى مصر، إلا أن فرسان جزيرة رودس علموا بذلك وقاموا بالإغارة على سفنه وأحرقوها، فسحب عروج جنوده إلى البر وصرفهم إلى بلدانهم، وتوجه هو إلى أنطاليا وأمر هناك بصناعة سفينة أغار بها على سواحل رودس، وعاد بعد ذلك إلى أنطاليا بعد أن نجى من هجوم آخر قام به فرسان رودس استولوا فيه على سفينته الخاصة وأحرقوا سفن بحارته. توجه عروج لاحقًا إلى مانيسا والتقى بالأمير العثماني قورقود بن بايزيد الثاني الذي أَهداهُ سفينتين حربيتين ووصاه بأن يذهب إلى غرب البحر الأبيض المتوسط لكي ينظر في أوضاع المسلمين الذين يقتلون من قبل الإسبان في الأندلس، وخرج بعد ذلك وخاض عدد من المعارك البحرية واستولى على عدد من السفن والغنائم، ورجع بها إلى ميديلي فكان في استقباله في الميناء أخويه إسحاق وخير الدين. وفي هذه الأثناء وصل خبر اعتلاء سليم الأول عرش الدولة العثمانية ومعاداته لأخيه قورقود الذي كان مقربًا من البحارة العثمانيين وبالخاصة عروج الذين كانت سفينته هدية من قورقود فخرج عروج على أثر ذلك وتوجه إلى الإسكندرية وكان ذلك تقريبًا في سنة 918هـ الموافقة لسنة 1513م.
في سنة 918هـ الموافقة لسنة 1513م توجه عروج من ميديلي إلى الإسكندرية وفي طريقه استولى في سواحل جزيرة كربة على سبع سفن، وقد كان محرجًا من السلطان قنصوه الغوري بسبب فقدانه للسفن التي منحها له فقام على أثر ذلك بإهداء جزء من الغنائم له التي غنمها في طريقه إليه. وفي ربيع سنة 1513م استأذن عروج من السلطان قنصوه الغوري في الخروج إلى الغزو فأذن له بذلك، فتوجه إلى إلى سواحل قبرص ومن هناك توجه نحو الغرب فوصل إلى جزيرة جربة بتونس. وبعد اعتلاء سليم الأول عرش الدولة العثمانية أصدر أمرًا بمنع الإبحار في شواطئ الأناضول وموانئها، وللتأكد من تنفيذ أمره عين قبطانًا يدعى "إسكندر باشا" الذي كان يضايق البحارة بدعوى أنهم من رجال الأمير قورقود -الذي كان مقربًا من البحارة العثمانيين- ولم يكن يسمح لهم بركوب البحر، وعندما بلغت أخباره لخير الدين قرر مغادرة ميديلي فشحن سفنه بالقمح ثم مضى بسرعة إلى طرابلس الشام حيث استبدل القمح بالشعير ثم ذهب إلى بروزة ثم توجه إلى جزيرة "أياموري" المقابلة لبروزة واشترى هناك سفينة أعجبته. ومن هناك اتجه إلى أخيه عروج في جزيرة جربة بتونس.
بينما كان الإخوة في جزيرة جربة اتفقوا على الاتجاه إلى تونس بنية الجهاد، ويذكر خير الدين في مذكراته أنهم قالوا قبل التوجه إليها: "ما دام الموت نهاية كل حي فليكن في سبيل الله". فدخل الأخوة عروج وخير الدين بالإضافة إلى "يحيى ريس" على سلطان تونس الحفصي أبو عبد الله محمد المتوكل وقالوا له: فوافق السلطان على ذلك ورحب بهم. أذن السلطان للبحارة الأتراك بالرسو في ميناء حلق الوادي فعملوا على تقوية مركزهم وحصنوه بشكل جيد، وأدركوا أهمية تونس وأهمية موقعها، وقد كان ميناء حلق الوادي متحكمًا في خليج تونس. قضى البحارة شتاء ذلك العام (1513م-1514م) هناك وعند حلول الربيع بدأوا بغزواتهم البحرية حتى بلغوا جزيرة سردينيا وهناك استولوا على سفينة أحد القراصنة كان فيها مائة وخمسون أسيراً. واستولوا على سفينة كبيرة أخرى كانت محملة بالقمح، وقد وجدوا القراصنة الموجودون عليها قد هربوا ولاذوا بالفرار على قواربهم، وفي الصباح التالي استولوا أيضاً على سفينتين أخريين إحداهما مشحونة بالعسل والزيتون والجبن، والأخرى سفينة جنوية كانت محملة بالحديد ثم رجعوا إلى تونس. كذلك تذكر بعض المراجع أن الإخوة بربروس استولوا على سفينتين تابعتين للبابا يوليوس الثاني بين كورسيكا وإلبا وقد كانت هاتين السفينتين عملاقتان بالمقارنة بسفن الإخوة بربروس (ربما تكون هذه الغزوة هي إحدى الغزوات السابقة) وبعد هذه الحادثة ذاع صيت عروج في كامل أوروبا.