Polycrystalline samples of the magnesium-rich intermetallic compounds RECuMg4 (RE = Dy, Ho, Er, Tm) were synthesized by reaction of the elements in sealed tantalum ampoules heated in a high-frequency induction furnace. Phase purity of the RECuMg4 phases was ascertained by powder X-ray diffraction patterns. Well-shaped single crystals of HoCuMg4 could be grown in a NaCl/KCl salt flux and the crystal structure was refined from single crystal X-ray diffraction data: TbCuMg4 structure-type, space group Cmmm, a = 1361.4(2), b = 2039.3(4), c = 384.62(6) pm. The crystal structure of the RECuMg4 phases can be understood as a complex intergrowth variant of CsCl and AlB2 related slabs. The remarkable crystal chemical motif concerns the orthorhombically distorted bcc-like magnesium cubes with Mg-Mg distances ranging from 306 to 334 pm. At high temperatures DyCuMg4 and ErCuMg4 are Curie-Weiss paramagnets with paramagnetic Curie-Weiss temperatures of -15 K and -2 K for RE = Dy and Er, respectively. The effective magnetic moments, 10.66μB for RE = Dy and 9.65μB for RE = Er prove stable trivalent ground states for the rare earth cations. Magnetic susceptibility and heat capacity measurements reveal long-range antiferromagnetic ordering at low temperatures (<21 K). Whereas DyCuMg4 exhibits two subsequent antiferromagnetic transitions at TN = 21 and 7.9 K which successively remove half of the entropy of a doublet crystal field ground state of Dy, ErCuMg4 shows a single, possibly broadened, antiferromagnetic transition at 8.6 K. The successive antiferromagnetic transitions are discussed with respect to magnetic frustration in the tetrameric units present in the crystal structure.