Recent theoretical and experimental studies have produced several unusual and interesting results on dense lithium, the first metal in the periodic table. These include the deviation from simple metal behaviour, superconductivity at 17 K, and a metal to semiconductor transition. Despite these efforts, at present there is no agreement on the location of the high-pressure solid phases and melting curve of Li, and there is no clear picture of its phase diagram above 50 GPa. Using powder and single-crystal high-pressure diffraction techniques, we have mapped out the lithium phase diagram up to 130 GPa over a wide temperature range between 77 and 300 K. Whereas the melting temperatures of materials usually rise under pressure, and even the lightest condensed gases, hydrogen and helium, melt at temperatures of the order of 103 K at 50 GPa, we find that at these pressures lithium remains a liquid at temperatures as low as 190 K, by far the lowest melting temperature observed for any material at such pressure. We also find that in its solid state above 60 GPa, lithium adopts three novel and complex crystal structures not previously observed in any element. Estimates of the zero-point energy suggest that quantum effects play a significant role in shaping the lithium phase diagram