Este trabalho desenvolve um modelo de busca por emprego com trabalhadores e firmas heterogêneos, salário mínimo e benefícios trabalhistas. Em equilíbrio, as firmas informais são menores, menos produtivas e empregam menos trabalhadores qualificados devido a um efeito de seleção. Trabalhadores informais geralmente recebem salários maiores para compensar a falta de benefícios trabalhistas, mas uma simples comparação de salários médios entre setores mostra um prêmio salarial para a formalidade devido a um efeito de composição. Além disto, o salário mínimo pode quebrar a relação de diferenciais compensatórios, de forma que haja um prêmio de formalidade para trabalhadores pouco qualificados mesmo após controlar para produtividade individual. O modelo é calibrado usando dados do Brasil e utilizado para explicar a evolução do mercado de trabalho neste país de 2003 até 2012. Os resultados sugerem que o aumento da escolaridade média foi o fator mais importante por trás da reversão da tendência de informalidade no Brasil, que ainda é um fato não plenamente explicado na literatura acadêmica. Também mostra-se que, no modelo calibrado, impostos progressivos sobre folha salarial poderiam levar a uma redução tanto do desemprego quanto da informalidade sem comprometer as receitas do governo.