Costly nominal wage adjustment has received renewed attention in the design of optimal policy. In this paper, we embed costly nominal wage adjustment into the modern theory of frictional labor markets to study optimal fiscal and monetary policy. The main result is that the optimal rate of price inflation is quite volatile despite the presence of nominal wage rigidities. This finding contrasts with results obtained in standard sticky-wage models, which employ neoclassical labor markets at their core. In addition, the tax-smoothing result that lies at the heart of optimal policy prescriptions in standard Ramsey models does not carry over to a search and bargaining environment. Both results stem from a common source in our model. Shared rents associated with the formation of long-term employment relationships imply that the optimal policy entails fluctuations in after-tax real wages much larger than in models with neoclassical labor markets, in which no such rent-sharing margin exists. The results demonstrate that the level at which nominal wage rigidity is modeled --- whether simply layered on top of a neoclassical market or articulated in the context of an explicit relationship between workers and firms --- can matter a great deal for policy recommendations.