Ultrasoft magnetorheological elastomers (MREs) offer convenient real-time magnetic field control of mechanical properties that provides a means to mimic mechanical cues and regulators of cells in vitro. Here, we systematically investigate the effect of polymer stiffness on magnetization reversal of MREs using a combination of magnetometry measurements and computational modeling. Poly-dimethylsiloxane-based MREs with Young’s moduli that range over two orders of magnitude were synthesized using commercial polymers Sylgard™ 527, Sylgard 184, and carbonyl iron powder. The magnetic hysteresis loops of the softer MREs exhibit a characteristic pinched loop shape with almost zero remanence and loop widening at intermediate fields that monotonically decreases with increasing polymer stiffness. A simple two-dipole model that incorporates magneto-mechanical coupling not only confirms that micrometer-scale particle motion along the applied magnetic field direction plays a defining role in the magnetic hysteresis of ultrasoft MREs but also reproduces the observed loop shapes and widening trends for MREs with varying polymer stiffnesses.