Iron is a major component of the cores of the Earth and inhabited exoplanets. Its phase diagram at extreme pressures (P) and temperatures (T) is the subject of extensive debate. While recent experiments provide evidence for the stability of the body-centered cubic (bcc) phase, several theoretical studies point to the stability (even though marginal) of the hexagonal close-packed phase (hcp). None of those studies considered the itinerant magnetism of iron at extreme conditions. We compute the high-pressure phase diagram of Fe using density functional theory-based molecular dynamics (DFT MD) in which the paramagnetic nature of Fe is treated within the model of thermally induced longitudinal spin fluctuations (LSF). The LSF DFT MD with 16 valence electrons favors bcc phase stability. Two-phase large-scale simulations with quantum accurate machine learning potentials provide us with both melting and hcp-bcc phase boundaries. The computed phase diagram agrees with most of the experimental data and solves most of the numerous controversies. We conclude that the account for magnetism results in the new physics of iron under extreme conditions and brings the theory in agreement with experiment and seismic data. We expect that the approach we use can be applied to other metals where itinerant magnetism is important.