We study the optimal provision of unemployment insurance (UI) over the business cycle. We consider an equilibrium Mortensen-Pissarides search and matching model with risk-averse workers and aggregate shocks to labor productivity. Both the vacancy creation decisions of firms and the search effort decisions of workers respond endogenously to aggregate shocks as well as to changes in UI policy. We characterize the optimal history-dependent UI policy. We find that, all else equal, the optimal benefit is decreasing in current productivity and decreasing in current unemployment.  Optimal benefits are therefore lowest when current productivity is high and current unemployment is high. The optimal path of benefits reacts non-monotonically to a productivity shock. Following a drop in productivity, benefits initially rise in order to provide short-run relief to the unemployed and stabilize wages, but then fall significantly below their pre-recession level, in order to speed up the subsequent recovery. Under the optimal policy, the path of benefits is pro-cyclical overall. As compared to the existing US UI system, the optimal history-dependent benefits smooth cyclical fluctuations in unemployment and deliver non-negligible welfare gains.