Highly educated labor force is one of the important resources in achieving social and economic development in every country. Tehran, as the capital city, has had the highest level of higher education graduates within the country. This paper aims to investigate socio-demographic factors affecting the employment of the graduates. Data come from a 2% sample of individual records of Iran's 2006 census. The target population contains all higher education graduates aged 20-34 years old. Findings show that the employment of male graduates has a significant relationship with demographic (age, marital status, life-time migration, and recent migration) and social (the level and the field of education) factors. For the female graduates, the dependent variable has a significant relationship with all independent variables except having a child, number of children, and recent migration. Multivariate analyses show that demographic variables, compared to social ones, have stronger power in predicting the probability of employment. This can be attributed to the lack of appropriate jobs, the influx of higher graduates, and gender inequality in the labor market.