Software enhancement must be carefully planned and quantified to satisfy customer change requests, such as adding a new functionality, or deleting or changing an existing one. This paper investigates the use of M5P Machine Learning (ML) algorithm on predicting software enhancement effort. This M5P ML algorithm is trained and tested with 302 software enhancement projects obtained from the ISBSG dataset. The correlation-based feature selection (CFS) algorithm is used to achieve efficient data reduction. Thus, the selected ML techniques are trained on a dataset with relevant features that lead to improve the accuracy of their estimates. The Performance of the M5P using CFS is compared with the three Machine Learning Regression Methods (MLRM): Gradient Boosting Regression (GBRegr), Linear Support Vector Regression (LinearSVR), and Random Forest Regression (RFR). Results show that the prediction of Software Enhancement Effort using Correlation-based Feature Selection and M5P is improved in terms of MAE (Mean Absolute Error) = 0.0612 and Root Mean Square Error (RMSE) = 0.2514.