Metastable structures of cobalt nitrides and Fe-substituted cobalt nitrides are explored as possible candidates for rare-earth free permanent magnets. Through crystal structure searches using an adaptive genetic algorithm, new structures of Co_nN (n = 3…8) are found to have lower energies than those previously discovered by experiments. Some structures exhibit large magnetic anisotropy energy, reaching as high as 200 μeV per Co atom (or 2.45 MJ m⁻³) based on first-principles density functional calculation. Substituting a fraction of Co with Fe helps in stabilizing new structures and at the same time further improves the magnetic properties. Our theoretical predictions provide useful insights into a promising system for the discovery of new rare-earth free magnets by experiment.