We propose a multiresolution GP to capture both long-range dependencies and abrupt changes. We hierarchically couple a collection of smooth GPs, each defined over an element of a random nested partition. Long-range dependencies are captured by the top-level GP while the partition points define the abrupt changes in the time series. Due to the inherent conjugacy of the GPs, one can analytically marginalize the GPs and compute the conditional probability of the observations given the partition tree. This allows for efficient inference of the partition itself, for which we employ graph-theoretic techniques. We analyze the theoretical properties of the multiresolution GP, as well as applying it to the analysis of Magnetoencephalography (MEG) recordings of brain activity.