As interest in new generations of nuclear reactors is increasing worldwide, development of accident tolerant fuel (ATF) cladding materials is crucial but suffers from large amounts of time and experimental efforts. Here, we present a strategy of the theory-guided bottom-up design of ATF cladding materials using ab initio calculations and the CALPHAD (CALculation of PHAse Diagrams) approach in combination with key experiments, which has been utilized to investigate the FeCrAl system. The thermochemical, physical and elastic mechanical properties, as well as the phase diagrams of the FeCrAl alloys, are well described using both modeling and experiment. Apart from the reported high-temperature steam oxidation resistance as the initial criterion, the present selection and optimization of the FeCrAl alloys as accident tolerant fuel cladding materials is based on three constraints: (i) single phase at 320 °C, a service temperature in a light water reactor; (ii) high melting point; (iii) good elastic mechanical property. Further optimization takes into account of alloy performance in literature. Consequently, a compositional range has been proposed as a guidance for the fabrication of new FeCrAl alloys, i.e., 0 at.% < Cr content ≤15 at.% and 11 at.% ≤ Al content ≤21 at.%. The present scheme may enhance the efficiency in designing new ATF cladding materials by promoting the discovery of the composition-structure-property-performance relationships.