We develop a search model of informal labor markets with realistic labor regulations, including minimum wage, and heterogeneous workers and firms. Smaller firms and lower wages in the informal sector emerge endogenously as firms and workers decide whether to comply with regulations. Because skilled and unskilled workers are imperfect substitutes in production, the model uniquely captures the informality consequences of shocks that affect returns to skill, such as rising educational levels. The model also reproduces empirical patterns incompatible with other frameworks: the presence of skilled and unskilled workers in the formal and informal sectors, the rising share of skilled workers by firm size, and formal and firm-size wage premiums that vary by skill level. We estimate the model using 2003 data from Brazil and show that it successfully predicts labor market changes observed between 2003 and 2012. Under a range of different assumptions, changes in workforce composition appear as the main drivers of the reduction in informality over this period. Policy simulations using the estimated model suggest that progressive payroll taxes are a cost-effective way to reduce informality.