A series of magnesium-substituted rare-earth metal germanides with a general formula RE5-xMgxGe4 (x approximate to 1.0-2.3; RE = Gd-Tm, Lu, Y) have been synthesized by high-temperature reactions and structurally characterized by single-crystal X-ray diffraction, These compounds crystallize with the common Gd5Si4 type structure in the orthorhombic space group Pnma (No. 62; Z = 4; Pearson's code oP36) and do not appear to undergo temperature-induced crystallographic phase transitions down to 120 K. Replacing rare-earth metal atoms with Mg, up to nearly 45% at., reduces the valence electron count and is clearly expressed in the subtle changes of the Ge-Ge and metal-metal bonding. Magnetization measurements as a function of the temperature and the applied field reveal complex magnetic structures at cryogenic temperatures and Curie-Weiss paramagnetic behavior at higher temperatures. The observed local moment magnetism is consistent with RE3+ ground states in all cases. In the magnetically ordered phases, the magnetization cannot reach saturation in fields up to 50 kOe. The structural trends across the series and the variations of the magnetic properties as a function of the Mg content are also discussed.