The influence of Al addition to the microstructure and specific mechanical properties of CrFeMoV-based quaternary high-entropy alloy (HEA) is investigated in this study. The designed AlxCrFeMoV alloys were fabricated through a powder metallurgy process using high-energy planetary ball milling followed by spark plasma sintering (SPS). Methanol (2.5 wt%) was used as a process aid during the mechanical alloying. Comprehensive microstructural examination revealed that the addition of Al led to the appearance of a BCC2 phase whose volume was directly related to the Al concentration. The experimental results were in good agreement with an inclusive thermodynamic analysis and predictions. The appearance of the BCC2 phase, and the strong bonding energy of Al and solid-solution strengthening in Al-containing systems, significantly enhanced the yield strength in compression from 2730 to 3552 MPa in the AlxCrFeMoV (x = 0 to 0.6) system at ambient temperature. The most notable feature of this study is the compressive strength that increased with decreasing density. The Al-1 (Alx where x = 1) alloy displayed a specific yield strength and hardness that are greater than those for any previously reported HEA, approaching 512 MPa∙cm3/g and 140 HV∙cm3/g, respectively.