Smart composite materials have been an active field of research in the last few decades. Magnetorheological elastomers (MREs) are examples of such smart composites and they show a coupling between magnetism and elasticity. MREs are heterogeneous materials and they consist of magnetic particles and a silicone-based elastomer. To describe and predict the behaviour of the macroscopic continuum accurately, microstructural information needs to be taken into account in the analysis of heterogeneous materials. Therefore, a combined approach called multi-scale analysis is used to consider various scales of observation simultaneously. The concept of Representative Volume Element (RVE) is typically employed by multi-scale approaches to describe the micro scale, and thus the size of RVE becomes a model parameter in such techniques. This has motivated the determination of the RVE size and the derivation of magnetoelastic constitutive relations in terms of the RVE sizes in our paper. The finite element method and a statistical analysis based on the coefficient of variation have been used to determine the RVE size of MREs. The results show that it is possible to determine a lower bound of the RVE size for an MRE. Furthermore, a parametric study has been conducted to examine the sensitivity of the RVE size on the different material properties of the constituents. It was found that the RVE size is primarily set by the contrast of the different material properties, i.e. the stiffness, permeability and magnetoelastic coupling coefficients.