High-entropy alloys (HEAs) are a new class of multi-component metallic alloys that recently have been introduced to the scientific community. As a result of their sometimes outstanding properties in regards to their mechanical behavior, as well as their corrosion and oxidation resistance, they have gained much interest as potential candidate alloys for future structural applications. The main work performed in this thesis was on one promising, high-performance, face-centered cubic alloy, CrCoNi, and two body-centered cubic HEAs, AlTiVNb and TiZrNbHfTa. These alloys were processed via high-pressure torsion in order to achieve a nanocrystalline microstructure and subsequently subjected to various annealing treatments. This was done for two reasons: I) The thermodynamic stability of the alloys could be probed by the ensuing microstructural investigations on the annealed samples. II) Microstructure-property relationships could be established by mechanical testing of the nanocrystalline and heat-treated materials. The performed studies were among the first to investigate these materials in the nanocrystalline state. It was demonstrated that in this grain size regime the CrCoNi alloy is competitive in regards to its performance in tensile tests with a comparable structural material, 316L steel. Additionally, the nanocrystalline TiZrNbHfTa alloy showed outstanding properties by retaining almost the same level of ductility compared to the coarse-grained material, while the tensile strength was more than doubled. By performing systematic annealing studies it could be shown that, while the investigated alloys were frequently believed to be stable, single-phase alloys, the (near) equilibrium microstructures of the alloys include multiple phases over an extended temperature range. This has important implications since, in the case of both bcc alloys, the ensuing phase decompositions lead to a strong deterioration of the mechanical properties, especially ductility. This could severely influence their feasibility as structural materials. Interestingly, the CrCoNi alloy was highly prone to abnormal grain growth, which enabled the possibility of engineering a bimodal distribution of grain sizes, a frequently suggested strategy to reach outstanding combinations of strength and ductility. By employing this method one microstructural state with an ultra-high tensile strength and a significantly increased elongation to failure compared to the nanocrystalline material could be achieved. In conclusion, the performed work sheds new light on the mechanical behavior as well as the microstructural and thermal stability of HEAs in the nanocrystalline grain size regime.