Innovation policy is increasingly informed from the perspective of a national innovation system (NIS), but, despite the fact that research findings emphasize the importance of national differences in the framing conditions for innovation, policy prescriptions tend to be uniform. Justifications for innovation policy generally relate to notions of market failure that are applicable in all nations in all conditions. In this paper we develop a broad framework for NIS analysis, involving free market, coordination and complex-evolutionary system approaches. Within this framework we explore the evolving relationship between market failure and systems approaches to innovation policy in the case of Australia. Drawing on information and analysis collected for a major review of Australia's NIS, and the government's 10-year plan in response to it, we show how the free market trajectory of policy-making of past decades is being extended, complemented and refocused by new approaches to complex-evolutionary system thinking. These approaches are shown to emphasize the importance of systemic connectivity, evolving institutions and organizational capabilities. Nonetheless, despite the fact that there has been much progress in this direction in the Australian debate, the predominant logic behind policy choices still remains one of addressing market failure, and the primary focus of policy attention continues to be science and research rather than demand-led approaches. We discuss how the development and elaboration of notions of systems failure, rather than just market failure, can further improve policy-making in the future.