Rare earth free alloys are in focus of permanent magnet research since the accessibility of the elements needed for nowadays conventional magnets is limited. Tetragonally strained iron-cobalt (Fe-Co) has attracted large interest as promising candidate due to theoretical calculations. In experiments, however, the applied strain quickly relaxes with increasing film thickness and hampers stabilization of a strong magnetocrystalline anisotropy. In our study we show that already 2 at% of carbon substantially reduce the lattice relaxation leading to the formation of a spontaneously strained phase with 3 % tetragonal distortion. In these strained (Fe$_{0.4}$Co$_{0.6}$)$_{0.98}$C$_{0.02}$ films, a magnetocrystalline anisotropy above 0.4 MJ/m$^3$ is observed while the large polarization of 2.1 T is maintained. Compared to binary Fe-Co this is a remarkable improvement of the intrinsic magnetic properties. In this paper, we relate our experimental work to theoretical studies of strained Fe-Co-C and find a very good agreement.