Herein, we present an investigation on magnetostrictive phenomena in magnetorheological elastomers. By using a continuum approach, constitutive as well as geometric properties on the microscale are taken into account in order to predict the effective behavior of these composites by means of a computational homogenization. Thus, the magnetic and mechanical fields are resolved explicitly without the simplifying assumption of dipoles. In the present work, a modeling strategy which accounts for elastic constituents and a nonlinear magnetization behavior of the particles is pursued. In order to provide a better understanding of fundamental deformation mechanisms, idealized lattices as well as compact and wavy chains are considered within a first study. Our results confirm assumptions stated in the literature according to which macroscopic magnetostriction can be ascribed to microscopic particle movements that result in an improved microstructure. The simulations that are performed for the subsequent investigations on random microstructures with different particle-volume fractions are evaluated statistically to ensure validity of our findings. They reveal anisotropic as well as isotropic macroscopic behavior for structured and unstructured particle distributions, respectively. In view of the macroscopic magnetostriction, all the results presented in this contribution are in good agreement with current experimental and theoretical findings.