To identify the labor market reforms that offer the highest payoff, we develop a medium-scale two-country model representing a currency union featuring real and nominal rigidities and heterogeneous labor market frictions. A labor market reform is modeled as a permanent structural change in the labor market institutions. We find that changes in the domestic labor market can have drastic welfare implications for both countries. Welfare improvements are observed when a worker (a firm) is more likely to find a job (a worker) or when jobs are less likely to be destroyed. In addition, labor market heterogeneity has sizeable effects on the level of welfare gains. The more flexible the foreign labor market, the higher its welfare. Finally, we show that (i) the way the monetary authorities conduct their policy has negligible welfare effects and (ii) matching frictions can offset the negative effect of price rigidities in the economy.