The crystal structure of iron, the major component of the Earth's inner core (IC), is unknown under the IC high pressure (P) (3.3-3.6 Mbar) and temperature (T) (5000-7000 K). Experimental and theoretical data on the phase diagram of iron at these extreme PT conditions are contradictory. Applying quasi-ab initio and ab initio molecular dynamics we computed free energies of the body-centered cubic (bcc), hexagonal close-packed (hcp), and liquid phases. The ionic free energies, computed for the embedded-atom model, were corrected for electronic entropy. Such correction brings the melting temperatures of the hcp iron in very good agreement with previous ab initio data. This validates the calculation of the bcc phase, where fully ab initio treatment is not technically possible due to large sizes required for convergence. The resulting phase diagram shows stabilization of the bcc phase prior to melting in the pressure range of the IC. The melting temperature of the bcc phase is equal to 7190 K at the pressure 360 GPa.