We have gained insight into the internal degree of atomic disorder in isolated size-selected Fe nanoparticles (NPs) ( ∼ 2-6 nm in size) supported on SiO₂/Si(111) and Al₂O₃(0001) from precise measurements of the low-energy (low-E) part of the phonon density of states [PDOS, g(E)] via ⁵⁷Fe nuclear resonant inelastic x-ray scattering (NRIXS) combined with transmission electron microscopy (TEM) measurements. An intriguing size-dependent trend was observed, namely, an increase of the low-E excess density of phonon states (as compared to the PDOS of bulk bcc Fe) with increasing NP size. This is unexpected, since usually the enhancement of the density of low-E phonon modes is attributed to low-coordinated atoms at the NP surface, whose relative content increases with decreasing NP size due to the increase in the surface-to-volume ratio. Our NPs are covered by a Ti-coating layer, which essentially restores the local neighborhood of surface Fe atoms towards bulk-like coordination, reducing the surface effect. Our data can be qualitatively explained by the existence of low-coordinated Fe atoms located at grain boundaries or other defects with structural disorder in the interior of the large NPs ( ∼ 3-6 nm), while our small NPs ( ∼ 2 nm) are single grain and, therefore, characterized by a higher degree of structural order. This conclusion is corroborated by the observation of Debye behavior at low energy [g(E)  ∼  Eⁿ with n  ∼  2] for the small NPs, but non-Debye behavior (with n  ∼  1.4) for the large NPs. The PDOS was used to determine thermodynamic properties of the Fe NPs. Finally, our results demonstrate that, in combination with TEM, NRIXS is a suitable technique to investigate atomic disorder/defects in NPs. We anticipate that our findings are universal for similar NPs with bcc structure.