High entropy alloys (HEAs) and medium entropy alloys (MEAs) are new classes of materials, defined as alloys composed of five or more and four or fewer kinds, respectively, of alloying elements with (near-)equiatomic concentrations. In the present article, we reviewed our recent works on ultra-grain refinement of HEAs and MEAs. CoCrFeMnNi HEA and its sub-system MEAs were highly deformed by high-pressure torsion and subsequently annealed under various conditions to obtain fully-recrystallized microstructures with FCC single phase having different mean grain sizes. It was found that ultrafine-grained (UFG) microstructures could be easily obtained by simple thermomechanical processes. Grain size and chemical composition dependence on mechanical properties of the HEA and MEAs were evaluated by tensile tests at room temperature. UFG HEAs and MEAs exhibited characteristic phenomena, such as discontinuous yielding and extra-hardening, similar to other UFG metals. In addition, the UFG HEAs and MEAs showed better strength-ductility balance compared with conventional UFG metals. Friction stresses of HEAs and MEAs were determined from Hall-Petch relationships and found to be much higher than those of pure metals and dilute alloys having FCC structure. Analysis based on theoretical models suggested that the high friction stress reflected atomic-scale heterogeneity in HEAs and MEAs.