Multivariate time series with missing values are common in many areas, forinstance in healthcare and finance. To face this problem, modern dataimputation approaches should (a) be tailored to sequential data, (b) deal withhigh dimensional and complex data distributions, and (c) be based on theprobabilistic modeling paradigm for interpretability and confidence assessment.However, many current approaches fall short in at least one of these aspects.Drawing on advances in deep learning and scalable probabilistic modeling, wepropose a new deep sequential variational autoencoder approach fordimensionality reduction and data imputation. Temporal dependencies are modeledwith a Gaussian process prior and a Cauchy kernel to reflect multi-scaledynamics in the latent space. We furthermore use a structured variationalinference distribution that improves the scalability of the approach. Wedemonstrate that our model exhibits superior imputation performance onbenchmark tasks and challenging real-world medical data.