With the rapid development of new service computing types, such as cloud computing, the amount of Web services becomes increasingly massive, as well as the amount of Web services with the same or similar functions. One of the most important issues in high-quality Web services recommendation is to identify the QoS value of Web services. Traditional collaborative filtering approaches have been widely employed in QoS prediction and Web Service recommendation. However, they suffer from the sparse and noisy data issues, which definitely cause the low performance of QoS predictions. In order to attain high prediction performance, the paper proposes a novel sparse matrix factorization approach based on the Spatial-Temporal features of User-Service QoS matrix. In matrix factorization, the proposed model takes that similar network environment occurs between similar users in neighbor moment into consideration, and constructs a global and local structure similarity based sparse matrix factorization machine. With the decomposed factors, we can get a low rank matrix completion, which could help to eliminate the impacts of sparse and noisy data in QoS prediction. To evaluate the performance of the proposed approach, we conduct a set of extensive experiments using real-world dataset. The experimental results show that the proposed model outperforms the traditional collaborative filtering approaches (With MAE maximize decreases 3.25% and RMSE 6.65% comparing with NMF; MAE maximize decreases 3.67%, and RMSE 7.01% comparing with SVD), which indicates that it can effectively resolve sparse and noisy data issues.