We develop a New Keynesian (NK) model with endogenous price setting frequency. Whether a firm updates its price in a given period depends on an analysis of expected cost and benefits modelled by a discrete choice process. A firm decides to update the price when expected benefits outweigh expected cost and then resets the price optimally. As markups are countercyclical, the model predicts that prices are more flexible during expansions and less flexible during recessions. Our quantitative analysis shows that contrary to the standard NK model, the assumed price setting behaviour: is consistent with micro data on price setting frequency; gives rise to an accelerating Phillips curve that is steeper during expansions and flatter during recessions; explains shifts in the Phillips curve associated with different historical episodes without relying on implausible high cost-push shocks and nominal rigidities.