With the rapid development of new service computing types like cloud computing, the amount of Web services becomes increasingly massive, as is also the case for 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 proposed a novel sparse matrix factorization approach based on the spatial-temporal features of user-service QoS matrix,in which the proposed model took the occurence of similar network environment between similar users in neighbor moment into consideration, and constructed a global and local structure similarity based sparse matrix factorization machine. With the decomposed factors, we could get a low rank matrix completion, which helped to eliminate the impacts of sparse and noisy data in QoS prediction. To evaluate the performance of the proposed approach, a set of extensive experiments were conducted using real-world dataset. The experimental results show that the proposed model outperforms the traditional collaborative filtering approaches (the MAE value decreases by 3.25% and RMSE value by 6.65% compared with those of NMF; MAE value decreases by 3.67%, and RMSE by 7.01% compared with those of SVD), which indicates that it can effectively resolve sparse and noisy data issues.