Most existing magnetic hydrogels are weak and brittle. The development of strong and tough magnetic hydrogels would extend their applications into uncultivated areas, such as in actuators for soft machines and guided catheters for magnetic navigation systems, which is still a big challenge. Here a facile and versatile approach to fabricating highly stretchable, exceptionally tough and notch-insensitive magnetic hydrogels, Fe(3)O(4)@Fe-alginate/polyacrylamide (PAAm), is developed, by dispersing alginate-coated Fe(3)O(4) nanoparticles into the interpenetrating polymer networks of alginate and PAAm, with hybrid physical and chemical crosslinks. A cantilever bending beam actuator as well as a proof-of-concept magnetically guided hydrogel catheter is demonstrated. The method proposed in this work can be integrated into other strong and tough magnetic hydrogels for the development of novel hydrogel nanocomposites with both desirable functionality and superior mechanical properties.