Dictyostelium discoideum amoebas coordinate aggregation and morphogenesis by secreting cyclic adenosine monophosphate (cAMP) pulses that propagate as waves through fields of cells and multicellular structures. To retrace how this mechanism for self-organisation evolved, we studied the origin of the cAMP phosphodiesterase PdsA and its inhibitor PdiA, which are essential for cAMP wave propagation. D. discoideum and other species that use cAMP to aggregate reside in group 4 of the four major groups of Dictyostelia. We found that groups 1-3 express a non-specific, low affinity orthologue of PdsA, which gained cAMP selectivity and increased 200-fold in affinity in group 4. A low affinity group 3 PdsA only partially restored aggregation of a D. discoideum pdsA-null mutant, but was more effective at restoring fruiting body morphogenesis. Deletion of a group 2 PdsA gene resulted in disruption of fruiting body morphogenesis, but left aggregation unaffected. Together, these results show that groups 1-3 use a low affinity PdsA for morphogenesis that is neither suited nor required for aggregation. PdiA belongs to a family of matrix proteins that are present in all Dictyostelia and consist mainly of cysteine-rich repeats. However, in its current form with several extensively modified repeats, PdiA is only present in group 4. PdiA is essential for initiating spiral cAMP waves, which, by organising large territories, generate the large fruiting structures that characterise group 4. We conclude that efficient cAMP-mediated aggregation in group 4 evolved by recruitment and adaptation of a non-selective phosphodiesterase and a matrix component into a system for regulated cAMP degradation.