Despite rapidly rising female educational attainment and the closing if not reversal of the gender gap in education, female labor force participation rates in the MENA region remain low and stagnant, a phenomenon that has come to be known as the "MENA paradox." Even if increases in participation are observed, they are typically in the form of rising unemployment. We argue in this paper that female labor force participation among educated women in four MENA countries - Algeria, Egypt, Jordan and Tunisia - is constrained by adverse developments in the structure of employment opportunities on the demand side. Specifically, we argue that the contraction in public sector employment opportunities has not been made up by a commensurate increase in opportunities in the formal private sector, leading to increases in female unemployment or declines in participation. We use multinomial logit models estimated on annual labor force survey data by country to simulate trends in female participation in different labor market states (public sector, private wage work, non-wage work, unemployment and non-participation) for married and unmarried women of a given educational and age profile. Our results confirm that the decline in the probability of public sector employment for women with higher education is associated with either an increase in unemployment or a decline in participation.