The client-vendor relationship is a key success factor for information technology outsourcing projects. Although many studies have been published about this concept, many of them have focused on a set of particular elements and have not investigated the relationship and dependencies between them. This research paper provides an overview about existing challenges for client-vendor relationships and discovers relationships between them by applying the ISM methodology. We conducted a literature research to gather and analyze relevant articles and identified 11 relevant challenges. Based on the literature research and 20 questionnaire responses we gathered from experts, we used interpretive structural modelling to discover the relevance and the contextual relationships among the identified challenges. The findings of this study reveal that three challenges, namely (1) lack of experience, (2) lack of good management practices and processes, and (3) lack of contractual objects can be treated as key elements for establishing a client-vendor relationship. We discuss further research directions and explain why all other identified challenges have high dependencies on each other.