A series of electronic and structural transitions are predicted in molten lithium from first principles. A new phase with tetrahedral local order characteristic of sp3 bonded materials and poor electrical conductivity is found at pressures above 150 GPa and temperatures as high as 1000 K. Despite the lack of covalent bonding, weakly bound tetrahedral clusters with finite lifetimes are predicted to exist. The stabilization of this phase in lithium involves a unique mechanism of strong electron localization in interstitial regions and interactions among core electrons. The calculations provide evidence for anomalous melting above 20 GPa, with a melting temperature decreasing below 300 K, and point towards the existence of novel low-symmetry crystalline phases.