We develop an equilibrium model of on-the-job search with ex-ante heterogeneous workers and firms, aggregate uncertainty and vacancy creation. The model produces rich dynamics in which the distributions of unemployed workers, vacancies and worker-firm matches evolve stochastically over time. We prove that the surplus function, which fully characterizes the match value and the mobility decision of workers, does not depend on these distributions. We estimate the model on US labor market data from 1951-2007 and predict the fit for 2008-12. We use the model to measure the cyclicality of mismatch between workers and jobs.