Ab initio random structure searching and single-crystal x-ray diffraction have been used to determine the full structures of three phases of lithium, recently discovered at low temperature above 60 GPa. A structure with C2mb symmetry, calculated to be a poor metal, is proposed for the oC88 phase (60-65 GPa). The oC40 phase (65-95 GPa) is found to have a lowest-enthalpy structure with C2cb symmetry, in excellent agreement with the x-ray data. It is calculated to be a semiconductor with a band gap of similar to 1 eV at 90 GPa. oC24, stable above 95 GPa, has the space group Cmca, and refined atomic coordinates are in excellent agreement with previous calculations.