Applicability of coagulation-flocculation process by the Orchis mascula tuber starch as a novel natural coagulant was investigated for the first time in the treatment of oily-saline wastewater. Three inputs variables (pH, coagulant dose, and contact time) and two outputs of chemical oxygen demand (COD) and turbidity (TU) were studied for the proposed system. Orchis mascula tuber starch showed a remarkable performance on treatment of bilge water at the optimum conditions (4 mg L-1 of coagulants dose, pH of 5.0, and contact time of 15 min), with COD and TU removal efficiencies of 92.21% and 90.63%, respectively. Also, this material could remove the surfactant and oil-grease up to 23% and 93%, respectively. The face-centered central composite design-response surface methodology (FCCCD-RSM) and multivariate adaptive regression splines (MARS), which were used comparatively for the first time in the quantitative evaluation of the studied coagulation-flocculation process, revealed satisfactory predictive performances (R2 > 0.97) for both COD and TU removals. The kinetic study concluded that the second-order model performance was superior to the first-order model. Moreover, the bonding between the particles was also observed from the Fourier-transform infrared spectroscopy (FTIR) analysis of the Orchis mascula tuber starch.