Molybdenum (Mo) has been recognized as an essential alloying element of the MP35N (Co35.4Cr22.9Ni35.5Mo6.2, at.%) superalloy for enhancing strength and corrosion resistance. However, a full understanding of the addition of Mo on microstructure and mechanical properties of the Mo-free parent alloy is lacking. In this work, we consider five (Co37.7Cr24.4Ni37.9)100-xMox (x = 0, 0.7, 2.0, 3.2, and 6.2) alloys, and reveal that yield/tensile strength and ductility are continuously increased for these alloys with increasing Mo content while a single-phase face-centered cubic structure remains unchanged. It is found that strong solid solution strengthening (SSS) is a main domain to the improved yield strength, whereas grain boundaries are found to soften by the Mo addition. The first-principles calculations demonstrate that a severe local lattice distortion contributes to the enhanced SSS, and the grain boundary softening effect is mostly associated with the decreased shear modulus. Both first-principles calculations and scanning transmission electron microscopy observations reveal that the stacking fault energy (SFE) reduces by the Mo addition. The calculated SFE value decreases from 0.4 mJ/m2 to-11.8 mJ/m2 at 0 K as Mo content increases from 0 at.% to 6.2 at.%, and experimentally measured values of SFE at room temperature for both samples are about 18 mJ/m2 and 9 mJ/m2, respectively. The reduction of SFE promoted the generation of stacking faults and deformation twins, which sustain a high strain hardening rate, thus postponing necking instability and enhancing tensile strength and elongation.