We present an efficient workflow that combines multiscale (MS) forward simulation and stochastic gradient computation - MS-StoSAG - for the optimization of well controls applied to waterflooding under geological uncertainty. A two-stage iterative Multiscale Finite Volume (i-MSFV), a mass conservative reservoir simulation strategy, is employed as the forward simulation strategy. MS methods provide the ability to accurately capture fine scale heterogeneities, and thus the fine-scale physics of the problem, while solving for the primary variables in a more computationally efficient coarse-scale simulation grid. In the workflow, the construction of the basis fuctions is performed at an offline stage and they are not reconstructed/updated throughout the optimization process. Instead, inaccuracies due to outdated basis functions are addressed by the i-MSFV smoothing stage. The Stochastic Simplex Approximate Gradient (StoSAG) method, a stochastic gradient technique is employed to compute the gradient of the objective function using forward simulation responses. Our experiments illustrate that i-MSFV simulations provide accurate forward simulation responses for the gradient computation, with the advantage of speeding up the workflow due to faster simulations. Speed-ups up to a factor of five on the forward simulation, the most computationally expensive step of the optimization workflow, were achieved for the examples considered in the paper. Additionally, we investigate the impact of MS parameters such as coarsening ratio and heterogeneity contrast on the optimization process. The combination of speed and accuracy of MS forward simulation with the flexibility of the StoSAG technique allows for a flexible and efficient optimization workflow suitable for large-scale problems.@en