Despite significant advances in deep learning, probabilistic modeling of sequential data has remained challenging due to the interplay of high-dimensional inputs and temporal dynamics across long-distance time steps. In this dissertation, we propose deep probabilistic methods that model the temporal interactions between sequential inputs while accounting for the inherent uncertainty of future predictions. First, we study the problem of continual learning where samples of different classes arrive sequentially and incrementally, and propose a discriminative approach that uses random graphs to model sample similarities and guard against catastrophic forgetting. Second, we marry state space models with recent advances in deep learning architectures for the task of time series prediction, aiming to capture non-Markovian dynamics via latent variable models. Third, we extend such generative models to the challenging domain of videos in which both spatial and temporal signals are key to multi-frame video predictions. Empirical results show that our models perform competitively against recent baselines, bringing us one step closer to unlocking the underexplored potentials of sequential data.