Computer-controlled ultra-precision polishing technology is widely used for high-quality surface processing. However, its polishing tool has some shortcomings, such as limited adaptability to the complex surface and easy to cause surface damage. Therefore, a new smart material-based abrasive tool named magnetorheological elastic polishing composites (MREPCs) and its flexible polishing method are proposed. This study first prepared MREPCs and developed a polishing tool for MREPCs. Then, the material properties of MREPCs were obtained by theoretical and experimental analysis, and the tool influence function (TIF) of the hemispherical MRPECs was established according to the Hertz contact theory, the variable rheological theory and the Preston equation. Finally, the TIF and the polishing performance of MREPCs were verified by polishing experiments. The results show that the theoretical and the experimentally measured TIF models have a high coincidence, and the developed MREPCs can remove surface material with high precision. The above preliminary study indicates that MREPCs are promising for ultra-precision machining of small-sized parts with complex profiles.