Cellulose nanofibers (CNFs) are promising bio-based reinforcements for cement-based materials, improving microstructure and mechanical performance while supporting sustainable construction. However, experimental compressive-strength testing is costly and time-consuming across multiple mixture proportions and curing ages. This chapter develops a cross-validated machine learning framework to predict the compressive strength of CNF-reinforced cement-based composites using 695 experimental samples, comprising 196 concrete, 266 cement paste, and 233 cement mortar observations. Inputs included cement, water, CNFs, superplasticizer, fine aggregate, coarse aggregate, and curing age, depending on material type. Ten regression algorithms were evaluated, including linear, tree-based, kernel, neighbor-based, boosting, and bagging models. Standardization was incorporated within the modeling pipeline to prevent data leakage, while hyperparameters were optimized using RandomizedSearchCV with 5-fold cross-validation. Performance was further assessed using an independent 70/30 train-test split and repeated 5-fold cross-validation based on R2, MSE, RMSE, MAE, and MAPE. Nonlinear and ensemble models produced the most reliable predictions. For the combined dataset, bagging regression achieved the best test performance (R2 = 0.827, RMSE = 5.698 MPa, MAE = 3.838 MPa) and a cross-validation R2 of 0.810. Random forest performed best for concrete (R2 = 0.867; RMSE = 4.978 MPa), gradient boosting for cement paste (R2 = 0.700; RMSE = 8.500 MPa), and bagging for cement mortar (R2 = 0.724; RMSE = 4.315 MPa). Permutation importance showed that cement, water, curing age, CNFs, and aggregates contributed differently across material types. The framework enables rapid strength estimation and preliminary mixture design.