The Health in All Policies (HiAP) approach requires formal and sustained governance structures and mechanisms to ensure that the policies of various non-health sectors maximize positive and minimize negative impacts on population health. In this paper, we demonstrate the usefulness of a network perspective in understanding and contributing to the effectiveness of HiAP. We undertook an exploratory, qualitative case study of a HiAP structure in Iran, the Kerman province Council of Health and Food Security (CHFS) with diverse members from health and non-health sectors. We analyzed relevant policy texts and interviewed 32 policy actors involved in the CHFS. Data were analyzed using within-case analysis and constant comparative methodology. Our findings suggest that CHFS governance from a network perspective drew in practice on elements of two competing network governance modes: the network administrative organization (NAO) and the lead organization mode. Our results also show that a shift from a hierarchical and market-based mode of interaction to a network logic within CHFS has not yet taken place. In addition, CHFS suffers from large membership and an inability to address complex 'wicked problems', as well as low trust, legitimacy and goal consensus among its members. Drawing on other HiAP studies and commentaries, insights from organization network theory, and in-depth findings from our case study, we conclude that a NAO may be the most effective mode of governance for tackling complex social problems in HiAP structures. Since similar studies are limited, and our single case study may not be transferable across all contexts, we suggest that further research be undertaken to explore HiAP structures from a network perspective in different institutional and cultural settings. With increasing emphasis given to HiAP approaches in national and international health policy discourse, it is important that comparative knowledge about the effectiveness of HiAP governance arrangements be developed.