This paper proposes a novel variant of the Grey Wolf Optimization (GWO) algorithm, named Velocity-Aided Grey Wolf Optimizer (VAGWO). The original GWO lacks a velocity term in its position-updating procedure, and this is the main factor weakening the exploration capability of this algorithm. In VAGWO, this term is carefully set and incorporated into the updating formula of the GWO. Furthermore, both the exploration and exploitation capabilities of the GWO are enhanced in VAGWO via stressing the enlargement of steps that each leading wolf takes towards the others in the early iterations while stressing the reduction in these steps when approaching the later iterations. The VAGWO is compared with a set of popular and newly proposed meta-heuristic optimization algorithms through its implementation on a set of 13 high-dimensional shifted standard benchmark functions as well as 10 complex composition functions derived from the CEC2017 test suite and three engineering problems. The complexity of the proposed algorithm is also evaluated against the original GWO. The results indicate that the VAGWO is a computationally efficient algorithm, generating highly accurate results when employed to optimize high-dimensional and complex problems.