Japan’s so-called Lost Decade of the 1990s presents a unique case study of an economy with a recent severe and prolonged recession, with large changes in the labor market and fiscal policy as the main policy available to the government. Japanese unemployment rate surged from 2.1% in 1991 to 5.4% in 2002. Meanwhile, the Japanese economy experienced a rise in government expenditures, while taxes remained fairly stable. This paper quantitatively evaluates the impact of these changes in fiscal policies on labor market variables, in particular the unemployment rate, during the 1990s. We build, calibrate, and simulate a dynamic general equilibrium model with search frictions in the labor market, a productive government sector, heterogenous government spendings, and different categories of taxes. Our model is able to reproduce the paths of the main labor market variables, and the counterfactual experiments show that the changes that took place in the different spending components affected the unemployment rate heterogeneously, although overall they kept unemployment lower than it could have been. We also find that had the government also implemented countercyclical tax policies, unemployment would not have risen as much as it did by 2002.