The thermal behavior of free and alumina-supported iron-carbon nanoparticles is investigated via molecular-dynamics simulations, in which the effect of the substrate is treated with a simple Morse potential fitted to ab initio data. We observe that the presence of the substrate raises the melting temperature of medium and large Fe1-x Cx nanoparticles (x=0-0.16, N=80-1000, nonmagic numbers) by 40-60 K; it also plays an important role in defining the ground state of smaller Fe nanoparticles (N=50-80). The main focus of our study is the investigation of Fe-C phase diagrams as a function of the nanoparticle size. We find that as the cluster size decreases in the 1.1-1.6-nm -diameter range, the eutectic point shifts significantly not only toward lower temperatures, as expected from the Gibbs-Thomson law, but also toward lower concentrations of C. The strong dependence of the maximum C solubility on the Fe-C cluster size may have important implications for the catalytic growth of carbon nanotubes by chemical-vapor deposition. © 2007 The American Physical Society.