The methyl-substituted Al-based amidoborane Na[Al(CH3NHBH3)4] has been designed and synthesized as a potential candidate for hydrogen storage purposes. Its structure, as well as that of Na[AlH(CH3NHBH3)3], forming as an intermediate in mechanochemical synthesis, were determined by high-resolution powder X-ray diffraction. Synthesis of Na[Al(CH3NHBH3)4] requires much cheaper CH3NH2BH3 and undergoes under less harsh conditions compared to the unsubstituted analogue. Na[AlH(CH3NHBH3)3] is the first example of an Al-based compound containing both hydride and amidoborane species. Despite Na[Al(CH3NHBH3)4] is not suitable for hydrogen storage on its own, the reactive hydride composites (RHCs) made of Na[Al(CH3NHBH3)4] and 12 eqs. of NaH, or 6 eqs. of NaNH2 show the release of pure hydrogen at moderate temperatures, making this and similar systems interesting candidates for H-storage.