The observed shear-wave velocity VS in Earth's core is much lower than expected from mineralogical models derived from both calculations and experiments. A number of explanations have been proposed, but none sufficiently explain the seismological observations. Using ab initio molecular dynamics simulations, we obtained the elastic properties of hexagonal close-packed iron (hcp-Fe) at 360 gigapascals up to its melting temperature Tm. We found that Fe shows a strong nonlinear shear weakening just before melting (when T/Tm > 0.96), with a corresponding reduction in VS. Because temperatures range from T/Tm = 1 at the inner-outer core boundary to T/Tm ≈ 0.99 at the center, this strong nonlinear effect on VS should occur in the inner core, providing a compelling explanation for the low VS observed.