We investigate the pressure-temperature ($p$-$T$) phase diagram of elemental lithium (Li) up to multiterapascal (TPa) pressures using ab-initio random structure search (AIRSS) and density functional theory (DFT). At zero temperature, beyond the high-pressure $Fd\bar{3}m$ diamond structure predicted in previous studies, we find eleven solid-state phase transitions to structures of greatly varying complexity, in addition to two structures that we calculate will become stable with sufficient temperature. The full $p$-$T$ dependence of the phase boundaries are computed within the vibrational harmonic approximation, and the solid-liquid melting line is calculated using ab-initio molecular dynamics simulations. Notably, between 39.1 TPa and 55.7 TPa, Li adopts an elaborate monoclinic structure with 46 atoms in the primitive unit cell, and between 71.9 TPa and $103$ TPa, an incommensurate host-guest phase of the Ba-IV type. We find that Li, hitherto predicted to be an electride at TPa pressures, abruptly loses its electride character above 16 TPa, reverting back to normal metallic behaviour with a corresponding rise in the Fermi-level electronic density of states (eDOS) and broadening of the electronic bands.