In recent years, a great deal of attention has been devoted to iterative control as an efficient methodology for the design of highly-performing controllers. In this paper, we propose a new iterative scheme which explicitly accounts for the presence of uncertainty. At each step, the designed controller is the best possible one relative to the existing level of uncertainty and uncertainty is reduced through steps. In this way, the achieved performance rapidly improves from one step to the next, while preserving the robust stability of the closed-loop system. The controller design is performed at a low computational effort thanks to the use of randomized algorithms.