1478 yılında doğduğu tahmin edilen Barbaros Hayreddin Paşa, Midilli’nin fethinden sonra adaya yerleşen Vardar Yenicesi’nden Yakup isimli bir sipahizade ile gayrimüslim eşinin dört oğlundan bir tanesidir. Asıl ismi Hızır’dır. Ancak Batılılar onu kızıl sakal anlamına gelen Barbaros (Barbarossa/Barbarroja) adıyla tanımışlardır. Hızır Reis Osmanlı tarafında ise Yavuz Sultan Selim’in kendisine taktığı Hayreddin ismiyle bilinmektedir.