While ordered L12 or gamma prime precipitates in face centered cubic (FCC) based microstructures have been extensively used for strengthening nickel or cobalt base superalloys, and more recently in high entropy alloys (HEAs) or complex concentrated alloys (CCAs), the possibility of exploiting ordered B2 precipitates in FCC-based systems has been relatively less investigated. The present study shows the propensity of developing a heterogeneous microstructure, consisting of two different distributions of FCC grain sizes, and two different size scales of B2 precipitates, within an FCC-based Al0.5Co1.5CrFeNi1.5 HEA/CCA. This alloy composition has been designed using solution thermodynamics-based modeling such that it has a high phase fraction and solvus temperature of the B2 phase. The resulting heterogenous microstructure exhibited an approximately 400% increase in yield strength with respect to the single-phase FCC solid solution condition of the same alloy while maintaining very good tensile ductility ∼20%. Display omitted •The HEA/CCA Al0.5Co1.5CrFeNi1.5 has been identified as a candidate alloy for studying FCC + B2 microstructure.•Single phase FCC, FCC + L12 and FCC + B2 microstructures have been obtained in this alloy via thermomechanical processing.•Precipitation annealing directly after rolling resulted in a heterogeneous microstructure with multiple length scales of B2.•The heterogeneous microstructure results in a 400% increase in yield stress when compared to the single phase FCC condition.