Iodine added to iodide-based ionic liquids leads to dramatic changes of their physical properties which may have implications for technological applications. Here we study the phase diagram of 1-methyl 3-propylimidazolium iodide, the temperature versus iodine (I2) concentration. Above a threshold I2 concentration of 3.9 M, polyiodides are found to be the major determinant of the thermodynamic properties, where nucleation occurs at reduced temperatures leading to a crystalline phase followed by a nematic phase. At the highest concentrations and for increasing temperatures a phonon mode develops which gives indication of mesophases with both improved orientational order of the polyiodide chains and a degree of positional order close to melting. These novel results are important for the fundamental understanding of the physical properties in molten salts and for applications where ionic liquids are used as charge-transporting media such as in batteries and dye-sensitized solar cells.