We develop a search and matching model where firms and workers produce output that depends both on match-specific productivity and on worker-specific human capital. The human capital is accumulated while working but depreciates while searching for a job. Jobs can be formal or informal and firms post the formality status. The equilibrium is characterized by an endogenous steady state distribution of human capital and by an endogenous formality rate. The model is estimated on longitudinal labor market data for Mexico. Human capital accumulation on-the-job 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 the dynamics of human capital accumulation magnifies the negative impact on productivity of the labor market institutions that give raise to informality.