Materials with controllable stiffness are of great interest to many fields, including medicine and robotics. In this paper we develop a new type of variable stiffness material based on the combination of a rigid low-melting-point-alloy (LMPA) microstructure embedded in soft poly(dimethylsiloxane) (PDMS). This material can transition between rigid and soft states by controlling the phase of the LMPA through efficient, direct Joule-heating of the LMPA microstructure. The devices tested demonstrate a relative stiffness change of > 25x (elastic modulus is 40 MPa when LMPA is solid and 1.5 MPa when LMPA is liquid) and a fast transition from rigid to soft states (< 1 s) at low power (< 500 mW). Additionally, the material possesses inherent state (soft and rigid) and strain sensing (GF = 0.8) based on resistance changes.