Portfolio optimization models are usually based on several distribution characteristics, such as mean, variance or Conditional Value-at-Risk (CVaR). For instance, the mean-variance approach uses mean and covariance matrix of return of instruments of a portfolio. However this conventional approach ignores tails of return distribution, which may be quite important for the portfolio evaluation. This chapter considers the portfolio optimization problems with the Stochastic Dominance constraints. As a distribution-free decision rule, Stochastic Dominance takes into account the entire distribution of return rather than some specific characteristic, such as variance. We implemented efficient numerical algorithms for solving the optimization problems with the Second-Order Stochastic Dominance (SSD) constraints and found portfolios of stocks dominating Dow Jones and DAX indices. We also compared portfolio optimization with SSD constraints with the Minimum Variance and Mean-Variance portfolio optimization.