The formation and structure of the ordered phases of Li atoms adsorbed on the Mo(112) surface are investigated by performing first-principles density-functional calculations. Large inward relaxation for the first atomic interlayer distance of the clean Mo(112) surface is found. The vertical relaxations of the substrate are only little influenced by the adsorbed Li atoms. The magnitude of lateral shifts of atoms along the atomic rows is found to be small and in line with measured values. The energetics of chain structures of Li adatoms for coverages 0.125<~Θ<~1 monolayer is determined and the p(4×1) and p(2×1) adatom structures are found to be the most favored ones in agreement with experiment. The binding energy of Li atoms decreases with increasing coverage. The calculated work function changes with Li adatom coverage are in good agreement with experiment. The energy barriers for adatom diffusion are determined and the energetics of lateral interactions between adatoms is discussed.