Network relationships are significant for new firms’ competitive advantages and success since new and entrepreneurial opportunities are favored by diversity (Burt, 2004; Ireland et al., 2002; Cooper, 2002; Granovetter, 1973). However, to gain access to various resources held by other actors the firms would have to have an ability to develop and utilize inter-organizational relationships (Walter et al., 2006), called network capability (NC). Additionally, new ventures would increase their performance by using an entrepreneurial strategy (cf. Wiklund & Shepherd, 2003; Lumpkin & Dess, 2001). Firms using an entrepreneurial orientation (EO) have an ability to find or discover new opportunities creating different and competitive advantages (Wiklund & Shepherd, 2005). This is particularly true among start-ups having external ties providing scarce and valuable resources (Lee et al., 2001). However, we believe these associations are moderated by the venture’s complexity. The more complex the venture is internally (i.e. having low level of routines and analyzability) and externally (i.e. having immature markets) the stronger the relationship between NC, networks and EO, and performance will be. This study will hence combine these three dimensions to investigate how start-ups can obtain competitive advantages improving their performance by the use of an entrepreneurial strategy and participation in networks, a combination that has not previously been studied.