Robust optimization is typically based on repeated calls to a deterministic simulation program that aim at both propagating uncertainties and finding optimal design variables. Often in practice, the “simulator” is a computationally intensive software which makes the computational cost one of the principal obstacles to optimization in the presence of uncertainties. This article proposes a new efficient method for minimizing the mean of the objective function. The efficiency stems from the sampling criterion which simultaneously optimizes and propagates uncertainty in the model. Without loss of generality, simulation parameters are divided into two sets, the deterministic optimization variables and the random uncertain parameters. A kriging (Gaussian process regression) model of the simulator is built and a mean process is analytically derived from it. The proposed sampling criterion that yields both optimization and uncertain parameters is the one-step ahead minimum variance of the mean process at the maximizer of the expected improvement. The method is compared with Monte Carlo and kriging-based approaches on analytical test functions in two, four and six dimensions.