Transient rheological response of magnetoactive elastomers is experimentally studied using dynamic torsion at a fixed oscillation frequency in temporally stepwise changing magnetic fields and oscillation amplitudes. For step magnetic-field excitations, at least three exponential functions are required to reasonably describe the time behavior of the storage shear modulus over long time scales (>10(3) s). The deduced characteristic time constants of the corresponding rearrangement processes of the filler network differ approximately by one order of magnitude: τ1 ≲ 10(1) s, τ2 ∼ 10(2) s, and τ3 ∼ 10(3) s. The sudden imposition of the external magnetic field activates a very fast rearrangement process with the characteristic time under 10 s, which cannot be determined more precisely due to the measurement conditions. Even more peculiar transient behavior has been observed during pyramid excitations, when either the external magnetic field was first stepwise increased and then decreased in a staircase manner at a fixed strain amplitude γ or the strain amplitude γ was first stepwise increased and then decreased in a staircase manner at a fixed magnetic field. In particular, the so-called "cross-over effect" has been identified in both dynamical loading programs. This cross-over effect seems to be promoted by the application of the external magnetic field. The experimental results are discussed in the context of the specific rearrangement of the magnetic filler network under the simultaneous action of the external magnetic field and shear deformation. Striking similarities of the observed phenomena to the structural relaxation processes in glassy materials and to the jamming transition of granular materials are pointed out. The obtained results are important for fundamental understanding of material behavior in magnetic fields as well as for the development of devices on the basis of magnetoactive elastomeric materials.