Coordination among decision-makers of an organization, each responsible for a certain partition of an overall decision-problem, is of crucial relevance with respect to the overall performance obtained. Among the challenges of coordination in distributed decision-making systems (DDMS) is to understand how environmental conditions like, for example, the complexity of the decision-problem to be solved, the problem’s predictability and its dynamics shape the adaptation of coordination mechanisms. These challenges apply to DDMS resided by human decision-makers like firms as well as to systems of artificial agents as studied in the domain of multiagent systems (MAS). It is well known that coordination for increasing decision-problems and, accordingly, growing organizations is in a particular tension between shaping the search for new solutions and setting appropriate constraints to deal with increasing size and intraorganizational complexity. Against this background, the paper studies the adaptation of coordination in the course of growing decision-making organizations. For this, an agent-based simulation model based on the framework of NK fitness landscapes is employed. The study controls for different levels of complexity of the overall decision-problem, different strategies of search for new solutions, and different levels of cost of effort to implement new solutions. The results suggest that, with respect to the emerging coordination mode, complexity subtly interferes with the search strategy employed and cost of effort. In particular, results support the conjecture that increasing complexity leads to more hierarchical coordination. However, the search strategy shapes the predominance of hierarchy in favor of granting more autonomy to decentralized decision-makers. Moreover, the study reveals that the cost of effort for implementing new solutions in conjunction with the search strategy may remarkably affect the emerging form of coordination. This could explain differences in prevailing coordination modes across different branches or technologies or could explain the emergence of contextually inferior modes of coordination.