Among the RE-free magnets, the metastable tetragonal α''-Fe16N2 phase of iron nitrides have attracted considerable experimental and theoretical attentions due to low cost of Fe and high magnetization in α''-Fe16N2 thin films. Using adaptive genetic algorithm and first principles calculations, we have explored the structures and magnetic properties of Fe16-xCoxN2 alloys. We show that substituting Fe by Co in Fe16N2 with Co/Fe ratio ≤ 1 can greatly improve the magnetic anisotropy of the material. The magnetocrystalline anisotropy energy from first-principles calculations reaches 3.18 MJ/m3 (245.6 μeV per metal atom) for Fe12Co4N2, much larger than that of Fe16N2 and is one of the largest among the reported rare-earth free magnets. From our systematic crystal structure searches, we show that there is a structure transition from tetragonal Fe16N2 to cubic Co16N2 as the function of Co concentration, which can be well explained by electron counting analysis. Different magnetic properties between the Fe-rich (x ≤ 8) and Co-rich (x > 8) Fe16-xCoxN2 is closely related to the structural transition. Some of the calculation results can be seen from the following figure. The promising structures predicted by our calculations would be validated by our experimental partner at University of Nebraska-Lincoln in future studies.