Hayreddín (también lo podemos encontrar como Jeireddín, Haradín, Khair-ed Din o Hayr al-Din) nació en Mitilene, en la isla de Lesbos, en 1475, que entonces estaba bajo el control del Imperio otomano.
Es conocido como Barbarroja, apodo que heredó de su hermano por tener el pelo y la barba de color rojizo; también se dice que el apodo fue otorgado por los italianos debido a unas variaciones lingüísticas de su título honorífico de Baba Oruç.
Las fuentes cuentan que Barbarroja nació en el seno de una familia de renegados por la siguiente historia. El padre de Hayreddín, llamado Yakup, vivía en Grecia y, cuando los turcos tomaron el país alrededor del año 1460, se lo llevaron a Constantinopla, lo hicieron turco y lo pusieron al servicio del sultán. Un día cometió un delito y, por miedo al castigo, huyó a Mitilene, quedando como renegado ante los turcos. Allí se casó con una mujer cristiana llamada Catalina, de la que se dice que era viuda de un sacerdote y que tenía marido y tres hijos. El matrimonio tuvo seis hijos: dos niñas -de las que no se sabe prácticamente nada- y cuatro niños. El mayor de los varones se llamaba Aruj (también Omiche u Horuc), el segundo Ilías (o Jaça), el tercero Hayreddín y el último Isaac (o Mauçete). Por entonces, la tradición en las familias de religiones mixtas era que las hijas se convirtieran a la fe cristiana y los hijos a la islámica, hecho que ocurrió con los hijos de Yakup y Catalina.
Aunque pobre y renegado, Yakup quería que sus hijos fuesen virtuosos y que aprendiesen, por lo que les buscó oficios: Ilías se dedicó a la carpintería, Isaac a los estudios, Hayreddín se convirtió en alfarero y Aruj navegó con su padre para aprender a comerciar. Pero, a pesar de todo, con el tiempo los cuatro hermanos se convertirían en marineros del comercio internacional y en piratas del Mediterráneo.
Años más tarde, Yakup moriría dejando a su esposa Catalina, viuda por segunda vez, al cargo de sus hijos.