Untethered small-scale soft robots have been widely researched because they can be employed to perform wireless procedures via natural orifices in the human body, or other minimally invasive operations. Nevertheless, achieving untethered robotic motion remains challenging owing to the lack of an effective wireless actuation mechanism. To overcome this limitation, we propose a magnetically actuated walking soft robot based on paper and a chained magnetic-microparticle-embedded polymer actuator. The magnetic polymer actuator was prepared by combining Fe3O4 magnetic particles (MPs, diameter of ~50 nm) and silicon that are affected by a magnetic field; thereafter, the magnetic properties were quantified to achieve proper force and optimized according to the mass ratio, viscosity, and rotational speed of a spin coater. The fabricated polymer was utilized as a soft robot actuator that can be controlled using an external magnetic field, and paper was employed to construct the robot body with legs to achieve walking motion. To confirm the feasibility of the designed robot, the operating capability of the robot was analyzed through finite element simulation, and a walking experiment was conducted using electromagnetic actuation. The soft robot could be moved by varying the magnetic flux density and on–off state, and it demonstrated a maximum moving speed of 0.77 mm/s. Further studies on the proposed soft walking robot may advance the development of small-scale robots with diagnostic and therapeutic functionalities for application in biomedical fields.