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 and decreasing returns to scale 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, and the declining formal wage premium by skill level. 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 closely reproduces the decline in informality observed between 2003 and 2012. The change in the composition of the labor force appears as the main driving force behind this phenomenon. We illustrate the use of the model for policy analysis by assessing the effectiveness of a progressive payroll tax in reducing informality.