We study the optimal monetary policy problem in a New Keynesian economy with a zero lower bound (ZLB) on the nominal interest rate, when the steady state natural rate (r*) becomes permanently negative. We show that the optimal policy aims to approach gradually a new steady state with positive average inflation. Around that steady state, the optimal policy implies well defined (second-best) paths for inflation and output in response to shocks to the natural rate. Under plausible calibrations, the optimal policy implies that the nominal rate remains at its ZLB most of the time. Despite the latter feature, the central bank can implement the optimal outcome as a unique equilibrium by means of an appropriate nonlinear interest rate rule. In order to establish that result, we derive sufficient conditions for local determinacy in a general model with endogenous regime switches.