In this paper, we develop a distributionally robust portfolio optimization model where the robustness is to different dependency structures among the random losses. For a Frechet class of distributions with overlapping marginals, we show that the distributionally robust portfolio optimization problem is efficiently solvable with linear programming. To guarantee the existence of a joint multivariate distribution consistent with the overlapping marginal information, we make use of the graph theoretic – running intersection property. We use this property to develop a tight linear programming formulation. Lastly, we use a data-driven approach using real financial data to identify the Frechet class of distributions with overlapping marginals and then optimize the portfolio over this class of distributions. Our results show that the optimization models proposed in this paper improves on the sample based approach.