Magnetically actuated miniature machines can perform multimodal locomotion and programmable deformations. However, they are either solid magnetic elastomers with limited morphological adaptability or liquid material systems with low mechanical strength. Here, we report magnetoactive phase transitional matter (MPTM) composed of magnetic neodymium-iron-boron microparticles embedded in liquid metal. MPTMs can reversibly switch between solid and liquid phase by heating with alternating magnetic field or through ambient cooling. In this way, they uniquely combine high mechanical strength (strength, 21.2 MPa; stiffness, 1.98 GPa), high load capacity (able to bear 30 kg), and fast locomotion speed (>1.5 m/s) in the solid phase with excellent morphological adaptability (elongation, splitting, and merging) in the liquid phase. We demonstrate the unique capabilities of MPTMs by showing their dynamic shape reconfigurability by realizing smart soldering machines and universal screws for smart assembly and machines for foreign body removal and drug delivery in a model stomach.