Understanding causality is a challenging problem and often complicated by changing causal relationships over time or across environments. Climate patterns, for example, change over time with recurring seasonal trends, but at the same time they also depend on ecosystem variability and other environmental characteristics, and thus differ between datasets collected in multiple contexts. Existing methods for discovering causal graphs from time series either assume stationarity or can only account for temporal or spatial changes, but do not permit both at the same time, making them unaware of locations where the same causal relationships apply. In this work, we unify the three tasks of causal graph discovery in the non-stationary multi-context setting, of reconstructing temporal regimes, and of partitioning datasets and regimes into contexts where the same causal relationships hold. To construct a consistent score that forms the basis of our method, we employ the Minimum Description Length (MDL) principle, and develop the SPACETIME algorithm that can deal with both non-stationarity over time and heterogeneity across datasets. It discovers a temporal causal graph and regime changepoints in an iterative fashion from time series, using non-parametric functional modeling and conditional discrepancy tests to flexibly model causal relationships and their changes. Besides confirming that it performs favorably on synthetic data, we show that it provides insights into real-world data such as river-runoff measured at different catchments and biosphere-atmosphere interactions across ecosystems.