It is widely believed that the presence of a large informal sector increases the efficiency cost of social programs -- transfer and social insurance programs -- in developing countries. We evaluate such claims for policies that have been heavily studied in countries with low informality -- increases in unemployment insurance (UI) benefits. We introduce informal work opportunities into a canonical model of optimal UI that specifies the typical tradeoff between workers'' need for insurance and the efficiency cost from distorting their incentives to return to a formal job. We then combine the model with evidence drawn from comprehensive administrative data to quantify the efficiency cost of increases in potential UI duration in Brazil. We find evidence of behavioral responses to UI incentives, including informality responses. However, because reemployment rates in the formal sector are low to begin with, most beneficiaries would draw the UI benefits absent behavioral responses, and only a fraction of the cost of (longer) UI benefits is due to perverse incentive effects. As a result, the efficiency cost is relatively low, and in fact lower than comparable estimates for the US. We reinforce this finding by showing that the efficiency cost is also lower in labor markets with higher informality within Brazil. This is because formal reemployment rates are even lower in those labor markets absent behavioral responses. In sum, the results go against the conventional wisdom, and indicate that efficiency concerns may even become more relevant as an economy formalizes.