We develop a search model of informal labor markets with worker and firm heterogeneity, intra-firm bargaining with imperfect substitutability across types of workers, and a comprehensive set of labor regulations, including minimum wage. Stylized facts associated with the informal sector, such as smaller firms and lower wages, emerge endogenously as firms and workers decide whether to comply with regulations. Imperfect substitutability across types of workers, decreasing returns to scale, and convex vacancy-posting costs enable the model to reproduce empirical patterns incompatible with existing frameworks in the literature: the presence of skilled and unskilled workers in the formal and informal sectors, the rising share of skilled workers by firm size, the declining formal wage premium by skill, and the rising firm-size wage premium by skill. These features also allow us to analyze the equilibrium responses to changes in the demand and supply of different types of labor. We estimate the model using Brazilian data and show that it reproduces various margins of labor market changes observed between 2003 and 2012. The change in the composition of the labor force appears as the main driving force behind the reduction in informality. We illustrate the use of the model for policy analysis by assessing the effectiveness of a progressive payroll tax in reducing informality.