Fe-Al-based nanocomposites with a superalloy-type of microstructure constitute a very promising class of materials. They possess a great potential as an alternative to the currently used steel grades in high temperature applications. Intermetallics-containing nanocomposites, such as those with the Fe3Al compound being one of the phases, may open a way towards future automotive and energy-conversion technologies with lower fuel consumption and reduced environmental impact. We employ quantum-mechanical calculations to analyze relations between ordering tendencies of Al atoms in the disordered Fe-18.75at.% Al phase on one hand and thermodynamic, structural and magnetic properties of Fe-Al-based nanocomposites on the other. When comparing supercells modeling disordered Fe-Al phase with different atomic distribution of atoms we find out that the supercell without 1st and 2nd nearest neighbor Al-Al pairs has a lower energy than that mimicking a perfect disorder (a special quasi-random structure, SQS). Further, coherent interfaces with (001), (110) and (1-10) crystallographic orientations between Fe3Al compound and SQS Fe-Al phase have higher energies than those exhibiting atomic distribution without 1st and 2nd nearest neighbor Al-Al pairs.