This paper introduces the concept of coexistence for embodied artificial agents and argues that it is a prerequisite for long-term, in-the-wild interaction with humans. Contemporary embodied artificial agents excel in static, predefined tasks but fall short in dynamic and long-term interactions with humans. On the other hand, humans can adapt and evolve continuously, exploiting the situated knowledge embedded in their environment and other agents, thus contributing to meaningful interactions. We take an interdisciplinary approach at different levels of organization, drawing from biology and design theory, to understand how human and non-human organisms foster entities that coexist within their specific environments. Finally, we propose key research directions for the artificial intelligence community to develop coexisting embodied agents, focusing on the principles, hardware and learning methods responsible for shaping them.