The study of advanced artificial electromagnetic materials, known as metamaterials, provides a link from material science to theoretical and applied electrodynamics, as well as to electrical engineering. Being initially intended mainly to achieve negative refraction(1,2), the concept of metamaterials quickly covered a much broader range of applications, from microwaves to optics and even acoustics(3,4). In particular, nonlinear metamaterials established a new research direction(5-12) giving rise to fruitful ideas for tunable and active artificial materials(13-15). Here we introduce the concept of magnetoelastic metamaterials, where a new type of nonlinear response emerges from mutual interaction. This is achieved by providing a mechanical degree of freedom so that the electromagnetic interaction in the metamaterial lattice is coupled to elastic interaction. This enables the electromagnetically induced forces to change the metamaterial structure, dynamically tuning its effective properties. This concept leads to a new generation of metamaterials, and can be compared to such fundamental concepts of modern physics as optomechanics(16) of photonic structures or magnetoelasticity in magnetic materials.