One aspect of the call for democracy in the recent Arab region uprisings is the issue of women's rights and gender equality. Three cultural and ideological forces have continued to shape the gender discourse in Arab Muslim-majority societies. They are: "Islamic" teaching and local traditions concerning women's roles in a given society; Western, European colonial perception of women's rights; and finally national gender-related policy reforms. This paper examines the past and present status of women and gender-educational inequality in the Arab world with particular reference to Egypt and Tunisia, prior to and post colonialism. Special attention is given to colonial legacy and its influence on gender and education; to current gender practices in the social sphere with a focus on women's modesty ("hijab"); to international policies and national responses with regard to women's rights and finally to female participation in pre-university and higher education. These issues incorporate a discussion of cultural and religious constraints. The paper demonstrates similarities and differences between Egypt's and Tunisia's reform policies towards gender parity. It highlights the confrontation of conservative versus liberal ideologies that occurred in each country with the implementation of its gender-related reform policy.