We study the optimal monetary policy problem in a New Keynesian economy with a zero lower bound (ZLB) on the nominal interest rate, and in which the steady state natural rate (r*) is negative. We show that the optimal policy aims to approach gradually a steady state with positive average inflation. Around that steady state, inflation and output fluctuate optimally in response to shocks to the natural rate. The central bank can implement that optimal outcome by means of an appropriate state-contingent rule, even though in equilibrium the nominal rate remains at zero most (or all) of the time. In order to establish that result, we derive sufficient conditions for local determinacy in a more general model with endogenous regime switches.