In order to improve the cycling stability of a new rare-earth Mg-based hydrogen storage alloys, La0.7Mg0.3Ni2.65-xMn0.1Co0.75Alx (x=0.0-0.4) alloys were prepared to investigate the structure and electrochemical properties of these alloys. XRD and Rietveld analyses reveal that the alloys consist of a (La,Mg)Ni3 phase with rhombohedral PuNi3-type structure and a LaNi5 phase with hexagonal CaCu5-type structure. Electrochemical studies on these alloys indicate that their maximum discharge capacities were decreased from 400.7 mAh/g (x=0.0) to 335.6 mAh/g (x=0.4). However, the cycling stability of the alloy electrodes was significantly improved after Ni was partially replaced by Al. After 100 charge/discharge cycles, the discharge capacity retention was increased from 32.0% (x=0.0) to 73.8 % (x=0.3), which can be attributed to the formation of a dense oxide film on the alloy surface. Moreover, the high rate dischargeability measurements indicate that the electrochemical kinetic properties were deteriorated with increasing Al content owing to the presence of a dense oxide film of Al.