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. This result means the model is tractable and can be estimated. We illustrate the quantitative implications of the model by fitting to US aggregate labor market data from 1951–2012. The model has rich implications for the cyclical dynamics of the distribution of skills of the unemployed, the distribution of types of vacancies posted, and sorting between heterogeneous workers and firms. (JEL E24, E32, J24, J63, J64)