Multi-agent systems exploiting case-based reasoning techniques have to deal with the problem of retrieving episodes that are themselves distributed across a set of agents. From a Gestalt perspective, a good overall case may not be the one derived from the summation of best subcases. In this paper, we deal with issues involved in learning and exploiting the learned knowledge in multi-agent case-based systems. We propose a novel algorithm called OA *, which composes optimal overall cases from distributed case components, and prove its optimality. We then experiment with OA * in a transportation domain on a grid world. We provide empirical results that provide strong evidence of the effectiveness of OA * for the distributed case-based learning task.