Utilizing ab initio random structure searching, we investigated Li adsorption on MoS2 and hydrogen molecules on Li-decorated MoS2. In contrast to graphene, Li can be adsorbed on both sides of MoS2, with even stronger binding than on the single side. We found that high coverages of Li can be attained without Li clustering, which is essential for hydrogen storage and Li ion batteries. Moreover, regarding battery applications, Li diffusion was also found to be easy. The fully-lithiated MoS2 can then adsorb H2 with 4.4 wt%. Interestingly, our calculations revealed that hydrogen molecules can be dissociated at high Li coverage with a minimal energy barrier. We further showed that the dissociated hydrogen atom can readily diffuse on the surface, thus keeping the reaction site active. We therefore propose that Li-MoS2 could be an inexpensive alternative catalyst to noble metals in hydrogen dissociation reactions.