Informality is ubiquitous in the labor markets of developing countries, and requiring that firms formally register, pay taxes, and provide employee benefits stipulated in labor regulations to reduce such informality is challenging. However, a matched survey on employer-employee preferences suggests that mutually beneficial job benefits exist, and that encouraging their adoption might be feasible. Carefully designed discrete choice experiments on combinations of benefits related to compensation, leave and termination policies, working conditions, and accident insurance, along with incentives for employers, reveal the relative values that workers and employers attach to each benefit. The results show that workers tend to value advance notice for job termination and accident insurance, and that employers are not averse to providing these benefits. In contrast, workers find long working hours without overtime compensation to be highly undesirable, whereas many employers are generally unwilling to provide shorter hours or overtime pay unless they face the threat of fines or are offered substantial incentives for doing so. Our findings therefore suggest that encouraging the provision of termination notice and accident insurance may be relatively easy, but that increasing compliance with legal limits on working hours and overtime compensation is likely to require increased enforcement or substantial incentives.