The discovery of new magnetic materials is a big challenge in the field of modern materials science. We report the development of a new extension of the evolutionary algorithm USPEX, enabling the search for half-metals (materials that are metallic only in one spin channel) and hard magnetic materials. First, we enabled the simultaneous optimization of stoichiometries, crystal structures, and magnetic structures of stable phases. Second, we developed a new fitness function for half-metallic materials that can be used for predicting half-metals through an evolutionary algorithm. We used this extended technique to predict new, potentially hard magnets and rediscover known half-metals. In total, we report five promising hard magnets with high energy product (|BH|MAX), anisotropy field (Ha), and magnetic hardness (κ) and a few half-metal phases in the Cr-O system. A comparison of our predictions with experimental results, including the synthesis of a newly predicted antiferromagnetic material (WMnB2), shows the robustness of our technique.