Outsourcing is a good strategy for firms that need to reduce operating costs and improve competitiveness and it is important that firms scientifically select appropriate outsourcing providers. Some efforts have been made to find systematic ways to deal with outsourcing problems, but these efforts incorrectly assumed that the criteria used in the decision process are independent, which is not true in the real world. In this study, we propose a new hybrid multiple criteria decision-making (MCDM) model, which addresses the dependent relationships between the various criteria. The relations-structure among the criteria is built with the aid of the decision-making trial and evaluation laboratory (DEMATEL) method. Decision-makers tend to hold diverse opinions about their preferences due to incomplete information and knowledge, or inherent conflict between various departments. We further used the fuzzy preference programming and the analytic network process (ANP) to form a model for the selection of partners for outsourcing providers. The proposed model can help practitioners improve their decision making process, especially when criteria are numerous and inter-related. The method is demonstrated using data from a Taiwanese airline.