A study of California's water planning and management process, known as CALFED, offers insights into governance strategies that can deal with adaptive management of environmental resources in ways that conventional bureaucratic procedures cannot. CALFED created an informal policy-making system, engaging multiple agencies and stakeholders. The research is built on data from 5 years of field work that included interviews with participants, review of documents, and observation of meetings. We argue that CALFED can be seen as a self-organizing complex adaptive network (CAN) in which interactions were generally guided by collaborative heuristics. The case demonstrates several innovative governance practices, including new practices and norms for interactions among the agents, a distributed structure of information and decision making, a nonlinear planning method, self-organizing system behavior, and adaptation. An example of a resulting policy innovation, a method to provide real-time environmental use of water while protecting a reliable supply of water for agricultural and urban interests, is described. We outline how ideas about complex adaptive network governance differ from ideas about traditional governance. These differences result in ongoing tension and turbulence as they do for other self-organizing governance processes that operate in a context of traditional governance.