Abstract In the current work, the response of heterogeneous magnetorheological elastomers (MREs) which are loaded by external magnetic fields in the absence and also in the presence of free space is studied. A fully-coupled two-scale finite element computational homogenization procedure is used to derive the material response at the macro-scale from the averaged response of the underlying micro-scale problem. Different combinations of boundary conditions, that satisfy the Hill-Mandel condition and are based on the primary variables of the magneto-elastic enthalpy and energy functionals are applied to solve the micro-scale boundary value problem. Furthermore, the influences of various microstructures on the macroscopic response of the MREs are investigated. The results indicate that the choice of microscopic boundary conditions and microstructure types can significantly affect the macroscopic responses of MREs.