We present experimental evidence of surface induced disordering at magnetic FeCoPd nanoparticles during the L1(0)-A1 phase transition using high-resolution aberration-corrected electron microscopy and strain mapping. In situ electron diffraction studies show a narrow temperature range of fully ordered L1(0) structure. The order-disorder transition is size dependent and induces strong lattice deformation in outer part of the nanocrystals. The formation of unusually large strain of 20% is discussed in terms of core-shell structure formation with surface disordered layer and ordered core.