Tetragonal ([Formula: see text]) FeNi is a promising material for high-performance rare-earth-free permanent magnets. Pure tetragonal FeNi is very difficult to synthesize due to its low chemical order-disorder transition temperature ([Formula: see text] K), and thus one must consider alternative non-equilibrium processing routes and alloy design strategies that make the formation of tetragonal FeNi feasible. In this paper, we investigate by density functional theory as implemented in the exact muffin-tin orbitals method whether alloying FeNi with a suitable element can have a positive impact on the phase formation and ordering properties while largely maintaining its attractive intrinsic magnetic properties. We find that small amount of non-magnetic (Al and Ti) or magnetic (Cr and Co) elements increase the order-disorder transition temperature. Adding Mo to the Co-doped system further enhances the ordering temperature while the Curie temperature is decreased only by a few degrees. Our results show that alloying is a viable route to stabilizing the ordered tetragonal phase of FeNi.