A systematic structural analysis of FePt, CuAu, and Au icosahedral nanoparticles is presented. The uncovered particles are prepared by inert gas condensation and thermally equilibrated through in-flight optical annealing. Aberration-corrected high-resolution transmission electron microscopy reveals that the crystal lattice is significantly expanded near the particle surface. These experimental findings are corroborated by molecular statics simulations that show that this near-surface strain originates from both intrinsic strain due to the icosahedral structure and a partial segregation of the larger of the two alloy constituents to the particle surface.