We study the optimal provision of unemployment insurance (UI) over the business cycle. We use an equilibrium search and matching model with aggregate shocks to labor productivity, incorporating risk-averse workers, endogenous worker search effort decisions, and unemployment benefit expiration. We characterize the optimal UI policy, allowing both the benefit level and benefit duration to depend on the history of past aggregate shocks. We find that the optimal benefit is decreasing in current productivity and decreasing in current unemployment. 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 substantial welfare gains.