We argue that long-run inflation has nonlinear and state-dependent effects on unemployment, output, and welfare. Using panel data from the OECD, we document three correlations. First, there is a positive long-run relationship between anticipated inflation and unemployment. Second, there is also a positive correlation between anticipated inflation and unemployment volatility. Third, the long-run inflation-unemployment relationship is not only positive, but also stronger when unemployment is higher. We show that these correlations arise in a standard monetary search model with two shocks ？ productivity and monetary ？ and frictions in labor and goods markets. Inflation lowers the surplus from a worker-firm match, in turn making it sensitive to productivity shocks or to further increases in inflation. We calibrate the model to match the U.S. postwar labor market and monetary data, and show that it is consistent with observed cross-country correlations. The model implies that the welfare cost of inflation is nonlinear in the level of inflation and is amplified by the presence of aggregate shocks.