Spectrum prediction is a promising technology to infer unknown/unmeasured spectrum state from known/measured spectrum data, by exploiting the inherent correlations among them. This paper investigates spectrum prediction from a spectral-temporal two-dimensional perspective, with the primary objective to improve the prediction performance by jointly exploiting the correlations in both time and frequency domains. Moreover, a practical constraint is also considered that historical observations could be highly incomplete, due to hardware limitations and/or transmission loss. To tackle these unique challenges, we firstly study the spectral and temporal correlations in real-world spectrum measurement data. Then, we formulate the joint spectral-temporal spectrum prediction with incomplete historical observations as a matrix completion problem. To resolve this problem, a soft-impute algorithm is further introduced by leveraging the approximate low intrinsic-dimensionality of real-world spectrum data matrix. Numerical results confirm the effectiveness of the proposed scheme and demonstrate that it outperform state-of-the-art schemes.