Against the background of profound social and economic changes, this paper analyzes patterns of school-to-work transition for four cohorts of Egyptian school leaver during the period from 1970–2012. Using retrospective longitudinal data from the Egyptian Labor Market Panel Survey 2012 our analyses reveal for women a U-shaped and for men an L-shaped relationship between education and transition rates to first job. We also find a divergent role of education for access to different labor market segments. Specifically, there is a strong positive education gradient on the probability of finding a first job in the privileged public sector and a reversed effect for access to the private informal sector for both men and women. Regarding time trends we find, counter to what is often suspected, that later cohorts of school leaver do not make slower first employment transitions than earlier cohorts. Males from later cohort have even higher transition rates to first jobs than earlier cohorts. For men, returns to higher education are decreasing with respect to the transition rate to the first job and remain stable at positive levels with respect to public sector access probability. For women, returns to higher education remain stable at positive levels with respect to the transition rate to the first job and are strongly increasing with respect to public sector access probability. These differences reflect that alternative employment opportunities in the private sector are education- and gender-specific.