This study investigates the effect of cold rolling pre-deformation with different reductions on the microstructure and mechanical properties of a novel polycrystalline nickel-based superalloy with low stacking fault energy and precipitation strengthening. The results indicate that cold rolling pre-deformation introduces microscopic substructures in the alloy, including dislocations, anti-phase boundaries (APBs), stacking faults (SFs), and Lomer–Cottrell (L–C) locks. The content of these substructures is positively correlated with the pre-deformation reduction. When the predeformation reaches 15%, a small amount of deformation twins are introduced near the grain boundaries, and the content of deformation twins in the 25% pre-deformation specimen further increases. With increasing pre-deformation reduction, the room-temperature tensile strength and yield strength gradually increase, while the plasticity gradually decreases. Due to the presence of nano-twins and grain refinement in the 25% pre-deformation specimen, its strength is further improved compared to the 15% pre-deformation specimen, while its plasticity remains roughly consistent.