This Letter investigates traffic matrix (TM) prediction that is widely used in various network management tasks. To fastly and accurately attain timely TM estimation in large-scale networks, the authors propose a deep architecture based on LSTM recurrent neural networks (RNNs) to model the spatio-temporal features of network traffic and then propose a novel TM prediction approach based on deep LSTM RNNs and a linear regression model. By training and validating it on real-world data from Abilene network, the authors show that the proposed TM prediction approach can achieve state-of-the-art TM prediction performance.