In order to solve the data sparsity problem and enhance the recommendation accuracy, we proposed a new Matrix Factorization XGBoost (MFXGB) recommendation algorithm which combines the matrix factorization method and the XGBoost (eXtreme Gradient Boosting) algorithm. MFXGB algorithm uses the SVD++ algorithm (SVD, Singular Value Decomposition) to fill the user-item score matrix and then builds a supervised learning model to predict the user’s score. To reduce the computation time, we proposed to construct features based on the K-means clustering method. The results of the MovieLens dataset experiments show that the recommendation accuracy of the proposed MFXGB algorithm improves 8.91%, 10.18% and 11.79% respectively, compared with the three traditional algorithms.