One of the grand challenges in interventional cardiology and neuroradiology is to minimize the operation time and risk of damage during catheterization. These two factors drastically increase if the target location resides in small and tortuous vessels. Flow-driven microcatheters are capable of rapidly and safely navigating small arteries with complex anatomy. However, their navigation relies on proper perfusion, which is an important bottleneck in the treatment of pathologies that cause impaired flow conditions. This work introduces the first endovascular sensor-integrated soft robotic device that navigates sub-millimeter arteries by extracting propulsive power from external magnetic fields. To this end, a number of innovations are described in the design, actuation, and control of flexible magnetic structures. The device is capable of advancing inside vasculature in an automated fashion using an open-loop control scheme. Onboard sensors enable the real-time monitoring of flow conditions, and autonomous switching between different modes of locomotion. The potential of the presented technology for minimally invasive diagnosis and therapy is demonstrated by achieving navigation inside coronary arteries of an ex vivo porcine heart under fluoroscopic guidance.