International trade flows show strong persistence over time. This holds for yearly data and especially for higher-frequency data such as monthly data. Standard gravity theory cannot explain the persistence, i.e., why lagged trade flows should enter as an explanatory variable for current trade flows. We develop a structural dynamic gravity framework where the persistence stems from firms' sluggish adjustment of destination-specific prices, akin to sticky pricing in macroeconomics but with a bilateral focus. Our theoretical framework provides a micro-foundation for a gravity equation with lagged trade flows. We show that if persistence is ignored, standard gravity estimates of trade policy changes such as tariff cuts are initially biased downwards and then grow over time. As an alternative, we provide a two-part gravity estimation method to account for the persistence. Using OECD trade data at varying frequencies, we document the persistence of trade flows and estimate the share of firms that sluggishly adjust prices. Consistent with the literature on nominal rigidities, we find a high degree of price stickiness at monthly frequency and a lower degree at annual frequency. Our results help to explain the propagation of trade cost shocks to trade, prices and welfare over the short and long run. In addition, our model provides a mechanism that relates short-term to long-term (steady state) trade elasticities.