Our purpose in this article is to develop a robust optimization model which minimizes portfolio variance for a finite set of covariance matrices scenarios. The proposed approach aims at the proper selection of portfolios, in a way that for every covariance matrix estimate included in the analysis, the calculated portfolio variance remains as close to the corresponding individual minimum value, as possible. To accomplish this, we formulate a mixed-integer non-linear program with quadratic constraints. With respect to practical underlying concerns, investment policy constraints regarding the portfolio structure are also taken into consideration. The validity of the proposed approach is verified through extensive out-of-sample empirical testing in the EuroStoxx 50, the S&P 100, the S&P 500, as well as a well-diversified investment universe of ETFs. We report consistent generation of stable out-of-sample returns, which are in most cases superior to those of the worst-case scenario. Moreover, we provide strong evidence that the proposed robust model assists in selective asset picking and systematic avoidance of excessive losses.