Belkhodja was born in 1930 into a Tunisian family of Turkish origin who gave Tunisia a line of renowned theologians.^[1] At a young age, she took an early awareness of the deplorable condition of the Tunisian women through the attitude of her father. Although her father was devout to his wife and children, he shared a patriarchal attitude which the men of his generation were accustom too, which led him to deprive his daughters of education. When he died, Belkhodja was 13 years old and her education was limited to basic knowledge of religion and Arabic literature. As a teenager, she joined the first Tunisian Women's Association, the Union of Muslim Women. In 1954 she married Azzouz Rebai, a rising individual of Neo Destour.^[1] During Neo Destour's activism Belkhodja took part in meetings alongside Farhat Hached, and participated in events organized by the party as of 15 February 1952. She was arrested with other activists and was sentenced to eighteen months in prison. After Tunisia's independence, she became one of the founders of the Union Nationale de la Femme Tunisienne (UNFT) in 1958. Aisha Bellagha became the first president and Belkhodja the Secretary.^[1]