Cement stabilized soil (CSS) yields wide application as a routine cementitious material due to cost-effectiveness. However, the mechanical strength of CSS impedes development. This research assesses the feasible combined enhancement of unconfined compressive strength (UCS) and flexural strength (FS) of construction and demolition (C&D) waste, polypropylene fiber, and sodium sulfate. Moreover, machine learning (ML) techniques including Back Propagation Neural Network (BPNN) and Random Forest (FR) were applied to estimate UCS and FS based on the comprehensive dataset. The laboratory tests were conducted at 7-, 14-, and 28-day curing age, indicating the positive effect of cement, C&D waste, and sodium sulfate. The improvement caused by polypropylene fiber on FS was also evaluated from the 81 experimental results. In addition, the beetle antennae search (BAS) approach and 10-fold cross-validation were employed to automatically tune the hyperparameters, avoiding tedious effort. The consequent correlation coefficients (R) ranged from 0.9295 to 0.9717 for BPNN, and 0.9262 to 0.9877 for RF, respectively, indicating the accuracy and reliability of the prediction. K-Nearest Neighbor (KNN), logistic regression (LR), and multiple linear regression (MLR) were conducted to validate the BPNN and RF algorithms. Furthermore, box and Taylor diagrams proved the BAS-BPNN and BAS-RF as the best-performed model for UCS and FS prediction, respectively. The optimal mixture design was proposed as 30% cement, 20% C&D waste, 4% fiber, and 0.8% sodium sulfate based on the importance score for each variable.