This paper reports a novel eutectoid nano-lamellar (FCC + L12)/(BCC + B2) microstructure that has been discovered in a relatively simple Al0.3CoFeNi high entropy alloy (HEA) or complex concentrated alloy (CCA). This novel eutectoid nano-lamellar microstructure presumably results from the complex interplay between Al-mediated lattice distortion (due to its larger atomic radius) in a face-centered cubic (FCC) CoFeNi solid solution, and a chemical ordering tendency leading to precipitation of ordered phases such as L12 and B2. This eutectoid microstructure is a result of solid-state decomposition of the FCC matrix and therefore distinct from the commonly reported eutectic microstructure in HEAs which results from solidification. This novel nano-lamellar microstructure exhibits a tensile yield strength of 1074 MPa with a reasonable ductility of 8%. The same alloy can be tuned to form a more damage-tolerant FCC + B2 microstructure, retaining high tensile yield stress (~900 MPa) with appreciable tensile ductility (>20%), via annealing at 700 °C. Such tunability of microstructures with dramatically different mechanical properties can be effectively engineered in the same CCA, by exploiting the complex interplay between ordering tendencies and lattice distortion.