Inferring Dynamic Bayesian Networks (DBNs) from multivariate time series data is a key step towards the understanding of complex systems as it reveals impor- Tant dependency relationship underlying such systems. Most of the traditional approaches assume a "static" DBN. Yet in many relevant applications, such as those arising in biology and social sciences, the dependency structures may vary over time. In this paper, we intro- duce a sparse Markov-switching vector autoregressive model to capture the structural changes in the depen- dency relationships over time. Our approach accounts for such structural changes via a set of latent state vari- Ables, which are modeled by a discrete-time discrete- state Markov process. Assuming that the underlying structures are sparse, we estimate the networks at each state through the hierarchical Bayesian group Lasso, so as to efficiently capture dependencies with lags greater than one time unit. For computation, we develop an effi- cient algorithm based on the Expectation-Maximization method. We demonstrate the strength of our approach through simulation studies and a real data set concern- ing climate change. Copyright © 2012 by the Society for Industrial and Applied Mathematics.