The classic paradigm of physical metallurgy is that the addition of alloying elements to metals increases their strength. It is less known if the solution-hardening can occur in nano-scale objects, and it is totally unknown how alloying can impact the strength of defect-free faceted nanoparticles. Purely metallic defect-free nanoparticles exhibit an ultra-high strength approaching the theoretical limit. Tested in compression, they deform elastically until the nucleation of the first dislocation, after which they collapse into a pancake shape. Here, we show by experiments and atomistic simulations that the alloying of Ni nanoparticles with Co reduces their ultimate strength. This counter-intuitive solution-softening effect is explained by solute-induced local spatial variations of the resolved shear stress, causing premature dislocation nucleation. The subsequent particle deformation requires more work, making it tougher. The emerging compromise between strength and toughness makes alloy nanoparticles promising candidates for applications.