We investigated the structural, magnetic, and electronic properties of Bi2Se3 epilayers containing Fe grown on GaAs(111) by molecular beam epitaxy. It is shown that, in the window of growth parameters leading to Bi2Se3 epilayers with optimized quality, Fe atom clustering leads to the formation of FexSey inclusions. These objects have platelet shape and are embedded within Bi2Se3. Monoclinic Fe3Se4 is identified as the main secondary phase through detailed structural measurements. Due to the presence of the hard ferrimagnetic Fe3Se4 inclusions, the system exhibits a very large coercive field at low temperature and room temperature magnetic ordering. Despite this composite structure and the proximity of a magnetic phase, the surface electronic structure of Bi2Se3 is preserved, as shown by the persistence of a gapless Dirac cone at Gamma.