The CoCrFeNiAl0.3 high entropy alloy samples were produced by different ball milling strategies including mechanical mixing and mechanical alloying in combination with spark plasma sintering and hot extrusion. The microstructure evolution and phase formation were investigated in correlation to tensile mechanical properties. It was found that a mixture of FCC and BCC structured matrix, as well as intermediate multiphases (e.g., Cr-rich σ phase, B2-NiAl, L12-Ni3Al) were formed because of incomplete alloying during consolidation of the mechanically mixed powders. After homogenization treatment at 1423 K, a complete alloyed FCC matrix was formed due to the transformation from BCC to FCC as well as the dissolution of the intermediate phases. For the mechanically alloyed powders, a similar single phase FCC matrix with an averaged grain size of 784 nm was obtained when subjected to thermomechanical consolidation. The microstructure exhibited a good thermal stability (grain size: 789 nm) even after homogenization treatment, which was likely attributed to the pinning effects of the dispersed Al2O3 nanoparticles deriving from the in-situ reaction of Al and O during powder consolidation. The Al2O3 nanoparticles played a dominate role in tailoring the microstructure and then enhanced the mechanical properties by Orowan mechanism, leading to a good combination of yield strength and elongation to fracture of 950 MPa and 17.3%, respectively.