The lack of strength and damage tolerance can limit the applications of conventional soft magnetic materials (SMMs), particularly in mechanically loaded functional devices. Therefore, strengthening and toughening of SMMs is critically important. However, conventional strengthening concepts usually significantly deteriorate soft magnetic properties, due to Bloch wall interactions with the defects used for hardening. Here a novel concept to overcome this dilemma is proposed, by developing bulk SMMs with excellent mechanical and attractive soft magnetic properties through coherent and ordered nanoprecipitates (<15 nm) dispersed homogeneously within a face-centered cubic matrix of a non-equiatomic CoFeNiTaAl high-entropy alloy (HEA). Compared to the alloy in precipitate-free state, the alloy variant with a large volume fraction (>42%) of nanoprecipitates achieves significantly enhanced strength (≈1526 MPa) at good ductility (≈15%), while the coercivity is only marginally increased (<10.7 Oe). The ordered nanoprecipitates and the resulting dynamic microband refinement in the matrix significantly strengthen the HEAs, while full coherency between the nanoprecipitates and the matrix leads at the same time to the desired insignificant pinning of the magnetic domain walls. The findings provide guidance for developing new high-performance materials with an excellent combination of mechanical and soft magnetic properties as needed for the electrification of transport and industry.