Co-Zr amorphous alloys exhibit soft magnetic properties, whereas the Co-rich crystalline magnetic phases in this alloy system displayed a hard magnetic behavior. In this study, an initial two-phase Co-Zr composite with an overall composition of 75 at.% Co and 25 at.% Zr was processed by high-pressure torsion (HPT), and the effects of severe plastic deformation and subsequent thermal treatment on the composite’s structural evolution and its magnetic properties were investigated. HPT processing allowed us to achieve an amorphous microstructure with low coercivity in its as-deformed state. To further tune the alloy’s magnetic properties and study its crystallization behavior, various annealed states were investigated. The microstructural properties were correlated with the magnetic properties, and a decreasing coercivity with increasing annealing temperatures was observed despite the onset of crystallization in the amorphous alloy. At higher annealing temperatures, coercivity increased again. The results appear promising for obtaining tuneable rare-earth free magnetic materials by severe plastic deformation.