Spinodal decomposition is a key phase transition in advanced materials and a significant effort is paid to the quantitative modeling of the phenomenon. The initial materials condition is often assumed to be random during modeling, but this may be an oversimplification. In this work, the effect of solution treatment above the miscibility gap, on spinodal decomposition during subsequent aging, has been investigated for an Fe-46.5 at.% Cr alloy. By atom probe tomography (APT), it is found that different extents of quenched-in Cr clustering exist after solution treatments at different temperatures. The clustering is pronounced at 800 °C but decreases significantly with increasing temperature to 900 °C. Thermodynamic Monte Carlo simulations show that there is a difference in atomic short range order between the different solution treatment temperatures. By APT, it is, furthermore, found that the kinetics of spinodal decomposition at 500 °C, i.e., within the miscibility gap, is enhanced in the initial alloy condition, where Cr was less randomly distributed. These observations are supported by kinetic Monte Carlo simulations, predicting a similar but less pronounced qualitative effect on spinodal decomposition kinetics. Other possible reasons for the enhanced kinetics could be related to clustering of interstitial elements and/or sigma phase, but neither was found in the experiments. Nonetheless, the observations in this work suggest that it is necessary to implement a modeling strategy, where the initial structure is properly accounted for when simulating spinodal decomposition.