Noble metal-free heterogeneous catalysts are highly desired for selective and solvent-free oxidation reactions. However, their practical application has been greatly restricted by their moderate activity. Herein, the scalable synthesis of a noble metal-free (Fe,Co,Ni,Cu)₃O₄ medium entropy oxide (MEO) catalyst and its grafting on reduced graphene oxide (rGO) is detailed. X-ray diffraction (XRD) and scanning electron microscopy (SEM) analyses confirm the formation of a high entropy spinel oxide phase with inclusions of CuO particles as a secondary phase. This MEO@rGO catalyst exhibits excellent performance for solvent-free aerobic oxidation of toluene, with 18.2% conversion after 4 hours and over 90% selectivity for benzaldehyde, outperforming all previously reported catalysts, including those based on noble metals. A thorough analytical investigation reveals that the outstanding MEO@rGO activity is related to a synergistic effect between the multiple different cations in the MEO, its abundant oxygen vacancies and the active sites on rGO. In addition, four robust machine learning models including adaptive boosting–support vector regression (SVR), Random Forest, K-nearest neighbor and Extra tree are applied to predict selectivity. The Adaboost–SVR model best fits all the experimental data with an average absolute relative error of 0.09%. The proposed model is reliable as an effective predictor for selectivity and has great potential to be used in the chemical and petrochemical industries.