The traffic volumes between a set of Origins and Destinations (OD) pairs within a network become increasingly critical for network operations management, planning, provisioning and traffic engineering. However, in practice it is challenging to reliably measure traffic in the whole network. For example, because of flaws in the measurement systems and attacks launched in a network, missing data and outliers are unavoidable. It is thus important to recover the missing entries and identify errors from the partial direct measurements. Existing recovery methods cannot sufficiently capture the multi-dimensional and spatial-temporal features of traffic data, which lead to perform poorly for network traffic data estimation. Their recovery accuracy tends to be significantly worse in the presence of both high data loss rate and gross corruptions. To address this problem, we propose a novel robust spatio-temporal tensor recovery (STTR) method to deal with missing data and outliers. First, by taking advantage of the structure in all dimensions of the traffic data, we organize the traffic data as a multi-way array (i.e., tensor). Second, by taking into account network traffic spatiotemporal characteristic, we incorporate domain knowledge about the structure of the underlying traffic data for missing values recovery and outlier removal. The proposed STTR is evaluated on real-world traffic trace data. Experimental results demonstrate that our STTR can achieve significantly better performance compared with the state-of-the-art recovery methods.