In many real-world applications, we consider a system not in isolation but in multiple contexts with distribution shifts. This results in non-i.i.d. data which may contain spurious correlations that can heavily bias learning. Here, we are interested in modeling such data using a mixture of causal mechanisms. To this end, we consider the principle that causal mechanisms either remain invariant under distribution shift or change independently. While existing work formulates this idea using statistical independence, it is limited to discovering an equivalence class of the causal model unless additional assumptions are imposed. We propose using the algorithmic notion of independence, and introduce a nonparametric approach for discovering independent mechanisms using Gaussian processes. In empirical evaluations, we show that this approach allows to discover causal models beyond partially directed graphs while being robust to different data-generating processes.