In our search for an optimum soft magnet with excellent mechanical properties which can be used in applications centered around “electro mobility”, nanocrystalline CoCrFeNiGa_x (x = 0.5, 1.0) bulk high entropy alloys (HEA) were successfully produced by spark plasma sintering (SPS) at 1073 K of HEA powders produced by high energy ball milling (HEBM). SPS of non-equiatomic CoCrFeNiGa_0.5 particles results in the formation of a single-phase fcc bulk HEA, while for the equiatomic CoCrFeNiGa composition a mixture of bcc and fcc phases was found. For both compositions SEM/EDX analysis showed a predominant uniform distribution of the elements with only a small number of Cr-rich precipitates. High pressure torsion (HPT) of the bulk samples led to an increased homogeneity and a grain refinement: i.e., the crystallite size of the single fcc phase of CoCrFeNiGa_0.5 decreased by a factor of 3; the crystallite size of the bcc and fcc phases of CoCrFeNiGa—by a factor of 4 and 10, respectively. The lattice strains substantially increased by nearly the same extent. After HPT the saturation magnetization (M_s) of the fcc phase of CoCrFeNiGa_0.5 and its Curie temperature increased by 17% (up to 35 Am²/kg) and 31.5% (from 95 K to 125 K), respectively, whereas the coercivity decreased by a factor of 6. The overall M_s of the equiatomic CoCrFeNiGa decreased by 34% and 55% at 10 K and 300 K, respectively. At the same time the coercivity of CoCrFeNiGa increased by 50%. The HPT treatment of SPS-consolidated HEAs increased the Vickers hardness (H_v) by a factor of two (up to 5.632 ± 0.188) only for the non-equiatomic CoCrFeNiGa_0.5, while for the equiatomic composition, the H_v remained unchanged (6.343–6.425 GPa).