Metallic nanocrystals (NCs) can be synthesized with tailored nonequilibrium shapes to enhance desired properties, e.g., octahedral fcc metal NCs optimize catalytic activity associated with {111} facets. However, maintenance of optimized properties requires stability against thermal reshaping. Thus, we analyze the reshaping of truncated fcc metal octahedra mediated by surface diffusion using a stochastic atomistic-level model with energetic input parameters for Pd. The model describes NC thermodynamics by an effective nearest-neighbor interaction and includes a realistic treatment of diffusive hopping for undercoordinated surface atoms. Kinetic Monte Carlo simulation reveals that the effective barrier, Eeff, for the initial stage of reshaping is strongly tied to the degree of truncation of the vertices in the synthesized initial octahedral shapes. This feature is elucidated via exact analytic determination of the energy variation along the optimal reshaping pathway at low-temperature (T), which involves transfer of atoms from truncated {100} vertex facets to form new layers on {111} side facets. Deviations from predictions of the low-T analysis due to entropic effects are more prominent for higher T and larger NC sizes.