In this work, firstly magnetic pumice (Fe3O4@PMC) composite was prepared by chemical co-precipitation method. Afterward MoS2 decorated Fe3O4@PMC (MoS2@Fe3O4@PMC) with high catalytic efficiency was successfully synthesized to be used in the degradation of methyl orange (MO) in the presence of NaBH4. Several spectroscopic and microscopic analyses were carried out to better understand the surface characteristic properties of the catalyst. The effects and interactions of some influencing parameters (initial dye concentration (C-o, mg/L), NaBH4 amount (M), catalyst amount (mg/mL), and time (s)) on the degradation process were evaluated and optimized using response surface methodology (RSM). Under the obtained optimum conditions (C-o 12.62 mg/L, NaBH4 amount 0.38 M, catalyst amount 0.388 mg/mL, and time 150.34 s), the de-colorization efficiency for MO was found to be 98.66%. The obtained experimental data for degradation efficiency are in close agreement with statistically predicted values (96%). The reaction rate constant of the MoS2@Fe3O4@PMC catalyst, which has a high catalytic effect for MO degradation under optimum conditions, was calculated as 1.357 min(-1). Also, the apparent activation energy for the MO degradation was obtained to be 13.29 kJ/mol. Moreover, the obtained nanocomposite shows outstanding reusability and excellent catalytic activity even after five cycles, offering a facile and active process for the degradation of toxic organic pollutants in the presence of NaBH4. This study presents a fast, inexpensive, magnetically separable, reusable, and highly efficient catalyst for the degradation of pollutants in wastewater without any noble metal clusters.