The search for new magnetic materials with high magnetization and magnetocrystalline anisotropy is important for a wide range of applications including information and energy processing. There is only a limited number of naturally occurring magnetic compounds that are suitable. This situation stimulates an exploration of new phases that occur far from thermal-equilibrium conditions, but their stabilization is generally inhibited due to high positive formation energies. Here a nanocluster-deposition method has enabled the discovery of a set of new non-equilibrium Co-N intermetallic compounds. The experimental search was assisted by computational methods including adaptive-genetic-algorithm and electronic-structure calculations. Conventional wisdom is that the interstitial or substitutional solubility of N in Co is much lower than that in Fe and that N in Co in equilibrium alloys does not produce materials with significant magnetization and anisotropy. By contrast, our experiments identify new Co-N compounds with favorable magnetic properties including hexagonal Co3N nanoparticles with a high saturation magnetic polarization (Js = 1.28 T or 12.8 kG) and an appreciable uniaxial magnetocrystalline anisotropy (K1 = 1.01 MJ m-3 or 10.1 Mergs per cm3). This research provides a pathway for uncovering new magnetic compounds with computational efficiency beyond the existing materials database, which is significant for future technologies.