We study bounds on the Value-at-Risk (VaR) of a portfolio when besides the marginal distributions of the components its variance is also known, a situation that is of considerable interest in risk management. We discuss when the bounds are sharp (attainable) and also point out a new connection between the study of VaR bounds and the convex ordering of aggregate risk. This connection leads to the construction of an algorithm, called Extended Rearrangement Algorithm (ERA), that makes it possible to approximate sharp VaR bounds. We test the stability and the quality of the algorithm in several numerical examples. We apply the results to the case of credit risk portfolio models and verify that adding the variance constraint gives rise to significantly tighter bounds in all situations of interest.