I analyze optimal monetary policy in an economy with search and matching frictions in the labor market and staggered nominal wage and price contracts. In this framework, as opposed to the standard New Keynesian model, preset nominal wages need not have any effect on existing employment relationships. However, staggered bargaining of nominal wages distorts aggregate job creation and creates inefficient dispersion in hiring rates across firms. Targeting zero inflation (the optimal policy in the standard New Keynesian model) only magnifies these distortions. The optimal policy allows for non-zero inflation in response to real shocks, so as to reduce the rigidity of real wages. Quantitatively, the case against price stability as the sole goal of monetary policy turns out to be important.