International new ventures (INVs) are often characterized as relatively new and small firms, lacking resources, established brand image, and seeking internationalization early in their life. Being new to international markets, they face various challenges such as liability of newness, foreignness or outsider-ship and from limited knowledge to tackle the uncertainties that exist in foreign markets. Therefore, these firms face uphill tasks in their internationalization process, particularly gaining confidence of their potential customers, and finding acceptance to their products and services. Yet, a number of small and new firms chose to go abroad and seek growth. Prior studies suggest that such expansion is possible because of the entrepreneurial competence and the global outlook of the founders. Research also emphasizes the role of personal network of founders in growth of new ventures. Such firms can benefit from their access to network resources and their embeddedness in local technological clusters. Research further suggests that the survival and success of these firms is closely associated to their ability to offer innovative products and services to their clients. Yet, developing innovative products and services and finding customers in foreign markets is a complex process, particularly in the case of knowledge-intensive products and services as this may require proven capabilities and high resources commitments on intensive foreign market activities. To overcome resource and market challenges these firms may rely on their network contacts and relationships with clients. However, the extant literature is not clear whether and how small ventures can benefit from their relationships as it may not be sufficient to guarantee market success and would require serious efforts from the firm to benefit from them. We believe that only in certain conditions these relationships can yield desired benefit and be useful for the growth of small ventures. This may require understanding how relationships and network help small new ventures develop capabilities and overcome lack of product image and create acceptance for it: this is important for these firms as the cost of failure may be too high for a resource constrained small new firm. The aim is to investigate and present a conceptual framework to explain the relationship strategies that small and new firms employ in encountering various challenges they face in their internationalisation process and also present some practical suggestions to aid managerially relevant decisions. Interviews from three knowledge-intensive product/service firms, two start-up firm from India and an international new venture from Sweden, are analysed in order to understand the role of business relationships in the international market survival and growth of new venture firms in knowledge based industries. The selected cases had gone through internationalisation process and managed to survive in the international market. This study highlights the contextual influences on relationship strategies of small and new firms, such as their customer choice, knowledge and capability strategy, reputation building strategy. New venture founders, looking for international market opportunities can benefit from the findings of this study, as they can anticipate some of the challenges in relationship building and develop counter strategies in advance.