Implicit constitutive relations that characterize the response of elastic bodies have greatly enhanced the arsenal available at the disposal of the analyst working in the field of elasticity. This class of models were recently extended to describe electroelastic bodies by the present authors. In this paper, we extend the development of implicit constitutive relations to describe the behaviour of elastic bodies that respond to magnetic stimuli. The models that are developed provide a rational way to describe phenomena that have hitherto not been adequately described by the classical models that are in place. After developing implicit constitutive relations for magnetoelastic bodies undergoing large deformations, we consider the linearization of the models within the context of small displacement gradients. We then use the linearized model to describe experimentally observed phenomena which the classical linearized magnetoelastic models are incapable of doing. We also solve several boundary value problems within the context of the models that are developed: extension and shear of a slab, and radial inflation and extension of a cylinder.