Estimation errors in both the expected returns and the covariance matrix hamper the constructing of reliable portfolios within the Markowitz framework. Robust techniques that incorporate the uncertainty about the unknown parameters are suggested in the literature. We propose a modification as well as an extension of such a technique and compare both with another robust approach. In order to eliminate oversimplifications of Markowitz’ portfolio theory, we generalize the optimization framework to better emulate a more realistic investment environment. Because the adjusted optimization problem is no longer solvable with standard algorithms, we employ a hybrid heuristic to tackle this problem. Our empirical analysis is conducted with a moving time window for returns of the German stock index DAX100. The results of all three robust approaches yield more stable portfolio compositions than those of the original Markowitz framework. Moreover, the out-of-sample risk of the robust approaches is lower and less volatile while their returns are not necessarily smaller.