Coal-Fired Steam Power Plant (PLTU) Rembang is an important power plant in the Central Java electricity system. Like other coal-fired steam power plants, fuel cost is the most significant expense when operating the PLTU Rembang. During the 2019-2021 period, the average fuel cost was 73.88% of total costs. One of the ways to reduce fuel costs is by improving the accuracy of fuel demand planning. Fuel procurement planning is very dependent on the projected amount of electricity sales from power plant, which is largely determined by the power plant's Capacity Factor (CF). However, PLTU Rembang does not have any CF prediction modeling. This research developed and compared four prediction models: random forest regression, support vector regression, multiple polynomial regression, and multiple linear regression. Based on the comparison of validation from the four prediction model with MAPE and R-squared parameters, the multiple linear regression models is the best model, with the lowest MAPE of 7.83% and the highest R-squared of 0.8814. This multiple linear regression model can be used to predict the CF of PLTU Rembang in the future so that fuel demand planning is more accurate.