Using first-principles calculations, the hydrogen storage capacity of bimetal alloy nanostructures has been carried out. We select two stable structures, Al10Li8 and Al13Li20, as paradigms, where Li atoms are exposed and unsaturated on the surfaces of Al clusters. The advantages of these structures are: (1) Li atoms do not cluster on the surfaces of Al nanoclusters. (2) Al10 and Al13 are much lighter than previous studied systems C60 and C48B12. (3) Both Al10Li8 and Al13 are very stable magic clusters. We show that in these two systems each exposed Li atom is able to bind one H2 molecule. The average binding energies are 0.10 and 0.13 eV/H2, with gravimetric densities of 4.1 wt% and 7.5 wt%, respectively, nearly meet and exceed the requirement of 5.5 wt% set by DOE.