Learning from spatio-temporal data has numerous applications such as human-behavior analysis, object tracking, video compression, and physics simulation. However, existing methods still perform poorly on challenging video tasks suchas long-term forecasting. The gap partially is because these kinds of challenging tasks require learning long-term spatio-temporal correlations in the video sequence. We propose a higher-order convolutional LSTM model that can efficiently learn these correlations with a succinct representation of the history. Our model relies on a novel tensor-train module that performs prediction by combining convolutional features across time. To make computation and memory requirements feasible, we develop a novel convolutional tensor-train decomposition of the higher-ordermodel. This decomposition reduces the model complexity by jointly approximatinga sequence of convolutional kernels as a low-rank tensor-train factorization. Asa result, our model outperforms existing approaches but uses only a fraction of parameters, including the baseline models. Our results achieve state-of-the-artperformance in a wide range of applications and datasets, including the multi-stepsvideo prediction on the Moving-MNIST-2 and KTH action datasets as well as earlyactivity recognition on the Something-Something V2 dataset.