Given a finite set of m scenarios, computing a portfolio with the minimum value-at-risk (VaR) is computationally difficult: the portfolio VaR function is nonconvex, nonsmooth and has many local minimums. Instead of formulating an n-asset optimal VaR portfolio problem as minimizing a loss quantile function to determine the asset holding vector Rn, we consider it as a minimization problem in an augmented space Rn, with a linear objective function under a probability constraint. We then propose a new gradual nonconvexification penalty method, aiming to reach a global minimum of nonconvex minimization under the probability constraint. A continuously differentiable piecewise quadratic function is used to approximate step functions, the sum of which defines the probabilistic constraint. In an attempt to reach the global minimizer, we solve a sequence of minimization problems indexed by a parameter pk > 0, where -pk is the minimum curvature for the probability constraint approximation. As the indexing parameter increases, the approximation function for the probabilistic inequality constraint becomes more nonconvex. Furthermore, the solution of the kth optimization problem is used as the starting point of the (k+1)th problem. Our new method has three advantages. First, it is structurally simple. Second, it is efficient, since each function evaluation requires O(m) arithmetic operations. Third, a gradual nonconvexification process is designed to track the global minimum. Both historical and synthetic data are used to illustrate the efficacy of the proposed VaR minimization method. We compare our method with the quantile-based smoothed VaR method of Gaivoronski and Pflug in terms of VaR, CPU time and efficient frontiers. We show that our gradual nonconvexification penalty method yields a better minimal VaR portfolio. We show that the proposed method is computationally much more efficient, especially when the number of scenarios is large.