Modern high-performance permanent magnets are made from alloys of rare earth and transition metal elements, and large magnetization is achieved in the alloys with a high concentration of transition metals. We applied an evolutionary search scheme based on first-principles calculations to the Y-Co-B system and predicted 37 cobalt-rich compounds with a high probability of being stable. Focusing on remarkably cobalt-rich compounds, YCo16 and YCo20, we found that, although they are metastable phases, the phase stability is increased with an increase of temperature due to the contribution of vibrational entropy. The magnetization and Curie temperature are higher by 0.22 T and 204 K in YCo16 and by 0.29 T and 204 K in YCo20 than those of Y2Co17, which has been well studied as a strong magnetic compound.