It has long been popularly believed that the relationship between inflation and relative price variability (RPV) is positive and stable. Using disaggregated CPI data for the United States and Japan, however, this study finds that the relationship is neither linear nor stable over time. The overall relationship is approximately U-shaped around a nonzero threshold inflation rate. RPV therefore changes not with the inflation rate per se, but with the deviation of inflation from the threshold inflation rate. More importantly, the relationship is by no means stable over time but instead varies significantly in a way that coincides with regime changes of inflation or monetary policy. The relationship was positive during the period of high inflation of the 1970s and the early 1980s, as has been documented by a number of previous studies, whereas it takes a U-shape profile during the Great Moderation. The results are robust to the use of core inflation, which excludes the traditionally volatile prices of food and energy. This paper then presents a modified version of the Calvo-type sticky price model to describe the observed empirical regularities. Simulation experiments show that the modified Calvo model fits the data well, and that the underlying relationship hinges upon the degree of price rigidity, which is systematically related to inflation regime. For countries and periods with low inflation rates, the relationship takes a U-shape as price adjustment is more sticky. In a high-inflation environment, when price setting becomes more flexible, the U-shaped profile vanishes.