Coherent cuboidal B2 nanoprecipitation in body-centered cubic (BCC)-based high-entropy alloys (HEAs) is important for the improvement of mechanical strength. The present work primarily investigated the effect of Ti substitution for Al on the cuboidal B2 nanoprecipitates in BCC Al0.7NiCoFeCr2 HEAs. A series of (Al,Ti)0.7NiCoFeCr2 HEAs with different Al/Ti ratios were prepared by suction-cast processing, and their microstructures and mechanical properties were then characterized comprehensively. It was found that the substitution of Ti for Al can change the phase structures of ordered precipitation, from the B2-AlNi to a highly ordered L21-Ni2AlTi phase. Especially, a small amount addition of Ti (≤4.2 at.%, Al/Ti ratio ≥2/1) renders the HEAs with cuboidal L21 nanoparticles coherently precipitated into the BCC matrix, which is attributed to the moderate lattice misfit (ε = 0.5–0.6%) between BCC and L21 phases. HEAs with such coherent microstructures exhibit high compressive yield strength of about 1700–1800 MPa. When the Ti content reaches up to 6.25 at.%, the matrix of the alloy will be turned into the σ phase, rather than BCC, leading to a heavy brittleness.