A range of emerging applications, from adaptive spectrum sensing to proactive spectrum mobility, depend on the ability to foresee spectrum state evolution. Despite a number of studies appearing about spectrum prediction, fundamental issues still remain unresolved: 1) The existing studies do not explicitly account for anomalies, which may incur serious performance degradation; 2) they focus on the design of batch spectrum prediction algorithms, which limit the scalability to analyze massive spectrum data in real time; 3) they assume the historical data are complete, which may not hold in reality. To address these issues, we develop a Robust Online Spectrum Prediction (ROSP) framework, with incomplete and corrupted observations, in this paper. We first present data analytics of real-world spectrum measurements to reveal the correlation structures of spectrum evolution and to analyze the impact of anomalies on the rank distribution of spectrum matrices. Then, from a spectral–temporal 2-D perspective, we formulate the ROSP as a joint optimization problem of matrix completion and recovery by effectively integrating the time series forecasting techniques and develop an alternating direction optimization method to efficiently solve it. We apply ROSP to a wide range of real-world spectrum matrices of popular wireless services. Experiment results show that ROSP outperforms state-of-the-art spectrum prediction schemes.