This paper introduces the Big Five personality traits along with other covariates in a job search, matching and bargaining model and investigates how education and personality traits affect job search behavior and labor market outcomes. It develops and estimates a partial equilibrium search model in which personality traits can influence worker productivity, job offer arrival rates, job dissolution rates and the division of surplus from an employer-employee match. The estimation is based on the IZA Evaluation Dataset, a panel dataset on newly-unemployed individuals in Germany between 2007 and 2008. Model specification tests provide support for a model that allows job search parameters to be heterogeneous across individuals, varying with levels of education, birth cohort, personality traits and gender. We use the estimated model to decompose the sources of the gender wage gap. The results show that the gap arises largely because women's personality traits are valued differently than men's. Of the Big Five traits, conscientiousness and agreeableness emerge as the most important in explaining the gender wage gap.