Fe-Al-Ta alloys with the ternary Laves phase Ta(Fe0.5+x, Al0.5-x)2 are studied experimentally with the objective of clarifying the effect of Laves phase precipitation and atomic ordering on the deformation characteristics of such Fe-Al-base alloys. The present study concentrates on the hardening effect of the Laves phase in ordered and disordered Fe-Al-Ta alloys with Al contents between 16 and 45 at.% showing the A2 disorder or the DO3 or B2 order. Ta has a low solubility in Fe-Al alloys which is beneficial for slowing down precipitate coarsening. Small amounts of Laves phase together with atomic ordering increase the yield stress and affect ductility in a complex way. The alloys with 1% Ta exhibit a high oxidation resistance. The continuing work aims at adjusting the Al and Ta content for an optimum relation of high-temperature strength and low-temperature ductility with maintaining a sufficient oxidation resistance.