Co-adaptation (or co-evolution), the parallel feedback process by which agents continuously adapt to the changes induced by the adaptive actions of other agents, is a ubiquitous feature of complex adaptive systems, from eco-systems to economies. We wish to understand which general features of complex systems necessarily follow from the (meta)-dynamics of co-adaptation, and which features depend on the details of particular systems. To begin this project, we present a model of co-adaptation (“The Stigmergy Game”) which is designed to be as a priori featureless as possible, in order to help isolate and understand the naked consequences of co-adaptation. In the model, heterogeneous, co-adapting agents, observe, interact with and change the state of an environment. Agents do not, ab initio, directly interact with each other. Agents adapt by choosing among a set of random “strategies,” particular to each agent. Each strategy is a complete specification of an agent's actions and payoffs. A priori, all environmental states are equally likely and all strategies have payoffs that sum to zero, so without co-adaptation agents would on average have zero “wealth”. Nevertheless, the dynamics of co-adaptation generates a structured environment in which only a subset of environmental states appear with high probability (niches) and in which agents accrue positive wealth. Furthermore, although there are no direct agent-agent interactions, there are induced non-trivial inter-agent interactions mediated by the environment. As a function of the population size and the number of possible environmental states, the system can be in one of three dynamical regions. Implications for a basic understanding of complex adaptive systems are discussed.