Three kinds of bulk nanocrystalline Fe-24at%Al-Xat%C (X=1,2,4) alloy were produced from Fe and Al powders with addition of methanol by MA with subsequent SPS at 1273K under 64MPa. Their microstructure and mechanical properties were investigated. The compacts have the relative densities of 99.97% (1at%C) to 99.6% (4at%C). The structure of compacts with 1at%C is composed of Fe3Al grains of 1.5µm in diameter and nano k-carbides (Fe3AlC0.5) precipitates, while those of compacts with 2 and 4at%C are composed of nanocrystalline Fe3Al of about 80nm in diameter, nano k-carbides and a-grains of about 1µm in diameter. These structures have the good thermal stability, maintaining the nanostructure even at 973K. The mechanical properties of these compacts were measured by compression tests at R.T. to 973K. The compacts with 1at%C and 2at%C of this work perform the superior mechanical properties (e.g. yield strength of 2.15GPa and rupture strain of 0.14 for compact with 2at%C at R.T.) when compared with the ordinary Fe3Al casting (e.g. 380MPa and 0.12). They also exhibit no environmental embrittlement, which is one of fatal problems for the ordinary Fe3Al mateials.