Collective animal behavior studies have led the way in developing models that account for a large number of individuals, but mostly have considered situations in which alignment and attraction play a key role, such as in schooling and flocking. By quantifying how animals react to one another’s presence, when interaction is via conspecific avoidance rather than alignment or attraction, we present a mechanistic insight that enables us to link individual behavior and space use patterns. As animals respond to both current and past positions of their neighbors, the assumption that the relative location of individuals is statistically and history independent is not tenable, underscoring the limitations of traditional space use studies. We move beyond that assumption by constructing a framework to analyze spatial segregation of mobile animals when neighbor proximity may elicit a retreat, and by linking conspecific encounter rate to history-dependent avoidance behavior. Our approach rests on the knowledge that animals communicate by modifying the environment in which they live, providing a method to analyze social cohesion as stigmergy, a form of mediated animal–animal interaction. By considering a population of animals that mark the terrain as they move, we predict how the spatiotemporal patterns that emerge depend on the degree of stigmergy of the interaction processes. We find in particular that nonlocal decision rules may generate a nonmonotonic dependence of the animal encounter rate as a function of the tendency to retreat from locations recently visited by other conspecifics, which has fundamental implications for epidemic disease spread and animal sociality.