Counterfactual explanations are a prominent example of post-hoc interpretability methods in the explainable Artificial Intelligence (AI) research domain. Differently from other explanation methods, they offer the possibility to have recourse against unfavourable outcomes computed by machine learning models. However, in this paper we show that retraining machine learning models over time may invalidate the counterfactual explanations of their outcomes. We provide a formal definition of this phenomenon and we introduce a method, namely counterfactual data augmentation, to help improving the robustness of counterfactual explanations over time. We test our method in an empirical study where we simulate different model retraining scenarios. Our results show that counterfactual data augmentation improves the robustness of counterfactual explanations over time, therefore contributing to their use in real-world machine learning applications.