The aim of the present paper is to explore the role of structural and relational governance in conditions of innovation uncertainty and network heterogeneity in sustainability-oriented innovation networks. The explorative analysis of eighteen innovation networks leads to two important findings. It demonstrates the importance of internalization of stakeholders in the network to create stability in the newly established coalitions and to assure continuation of sustainability-oriented innovation. Also, it demonstrates that even in conditions of innovation, complementarity of structural and relational governance is important. Structural governance (formalization) increases clarity and understanding about partners' differences, reduces uncertainty and increases rational commitment in uncertain and heterogeneous conditions. Relational governance (trust) has a complementary role in this, because it requires time to develop trust in newly established innovation networks with limited previous cooperation. In addition to structural governance (rational commitment), relational governance (trust) is important to prevent attrition in the highly uncertain conditions.