It is well documented in developed economies that portfolio investment across national borders brings benefits of increasing returns and/or reducing risk. Dividing MENA stock markets into two main groups (oil producing and non-oil producing countries), this study examines the potential role of each group in providing diversification benefits for international investors. In addition, the behavior of the long and the short-run Efficient Frontiers (EFs) constructed by each of the sub-groups and the combined MENA markets is explored. Multi-objective international portfolio models are proposed under Mean-Variance and Mean-Lower Partial Moment frameworks, and the Multiple Fitness Function Genetic Algorithm (MFFGA) is used to find the EFs of optimal portfolios. The findings indicate that the stock markets of oil producing countries can be considered as a potential avenue for international portfolio diversification for investors not only from the same countries but also from the other MENA markets. It was also found that international portfolios constructed from the combination of MENA equity markets are more stable compared to the portfolios of sub-group markets. Further, the findings indicate that the behavior of short-term EFs in the MENA region cannot be predicted by the behavior of long-term EFs.