Khayr al-Din operated with his brother 'Aruj from the North African coast during the period of intensified conflict between Christian Iberian powers and Muslim communities of the Maghrib. After 'Aruj was defeated and killed by a Spanish force in 1518, Khayr al-Din remained in Algiers and reorganized their forces. He then expanded Ottoman-aligned control through the conquest of Bone and Constantine.

Khayr al-Din offered the territories under his control to the protection of the Ottoman sultan, an arrangement that was accepted. He received the title of beylerbey and benefited from the arrival of janissary infantry sent from Anatolia. In 1529, his forces captured the fortress of Algiers, ending the Spanish garrison's hold over the key harbor.

Under his leadership, Algiers became both a base for piracy and a commercial entrepôt. The harbor was improved to support these functions, linking naval warfare, privateering, and trade. In 1533 Khayr al-Din was summoned to Istanbul, where he became admiral of the Ottoman fleet, leaving the administration of Algiers to successive beylerbeys.