Privatisation and contracting out have exacerbated the silo effect associated with the existence of separate government departments and agencies. The gaps created by the lack of integration between service providers and government have led to a range of solutions known variously as whole of government, connecting government and joined-up government. These are pragmatic solutions. On the one hand they recognise the failure of current agendas to provide coordinated government services, and on the other, the reluctance of western governments to resume traditional service provision. It is significant that the models underlying much of the whole of government response in Australia originate from the joined-up approaches implemented in the UK. These focus on horizontal coordination in a unitary state (Chandler 2000). However, in a federation such as Australia, state governments are constitutionally responsible for important public services. Some of these responsibilities are shared with the federal government. Simply adopting horizontal solutions in Australia threatens to create new gaps. The challenge is to manage the accountability, governance and coordination issues arising from horizontal whole of government initiatives. This paper outlines the issues facing the Australian federation in implementing whole of government models and argues that, in the process of accommodating these initiatives within its federal structure, it is finally reinventing government.