We develop a search and matching model where firms and workers are allowed to form matches (jobs) that can be formal or informal. Workers optimally choose the level of schooling acquired before entering the labor market and whether searching for a job as unemployed or as self-employed. Firms optimally decide the formality status of the job and bargain with workers over wages. The resulting equilibrium size of the informal sector is an endogenous function of labor market parameters and institutions. We focus on an increasingly important institution: a "dual" social protection system whereby contributory benefits in the formal sector coexist with non-contributory benefits in the informal sector. We estimate preferences for the system – together with all the other structural parameters of the labor market – using labor force survey data from Mexico and the time-staggered entry across municipalities of a non-contributory social program. Policy experiments show that informality may be reduced by either increasing or decreasing the payroll tax rate in the formal sector. They also show that a universal social security benefit system would decrease informality, incentivize schooling, and increase productivity at a relative fiscal cost that is similar to the one generated by the current system.