We develop a search and matching model where firms and workers produce output that depends both on match-specific productivity and worker-specific human capital. The human capital is accumulated while working but depreciates while searching for a job. Jobs can be formal or informal. The model is estimated on labor market data for Mexico. Human capital accumulation is responsible for more than half of the overall value of production, and upgrades more quickly while working formally than informally. Policy experiments reveal that human capital accumulation magnifies the negative impact on productivity of the labor market institutions that give rise to informality.