Ultra-fine-grained CoNiMo alloys with varying Mo contents (12, 15, and 18 at.%) were fabricated through high-pressure torsion followed by short-time annealing. The alloys exhibited complex lamellar structures within the grain interiors, characterized by a high density of coherent twin boundaries and interfaces between face-centered cubic and hexagonal close-packed phases. Refinement of complex lamellar structure with increasing Mo content leads to significant improvements in tensile properties, achieving a tensile strength of 1680 MPa and a uniform elongation of 11.7%. The enhanced strain-hardening behavior is attributed to the dislocation storage capability of the complex lamellar structure and heterogeneous deformation between the face-centered cubic and hexagonal close-packed phases. This work demonstrates the synergistic effects of massive boundaries with strong coherency and heterogeneous deformation to overcome the strength–ductility trade-off in metallic materials.