Cooperation among individuals is necessary for evolutionary transitions to higher levels of biological organization. In such transitions, groups of individuals at one level (such as single cells) cooperate to form selective units at a higher level (such as multicellular organisms). Though the evolution of cooperation is difficult to observe directly in higher eukaryotes, microorganisms do offer such an opportunity. Here we report the evolution of novel cooperative behaviour in experimental lineages of the bacterium Myxococcus xanthus. Wild-type strains of M. xanthus exhibit socially dependent swarming across soft surfaces by a mechanism known as 'S-motility' that requires the presence of extracellular type IV pili. In lineages of M. xanthus unable to make pili, a new mechanistic basis for cooperative swarming evolved. Evolved swarming is mediated, at least in part, by enhanced production of an extracellular fibril matrix that binds cells-and their evolutionary interests-together. Though costly to individuals, fibril production greatly enhanced population expansion in groups of interconnected cells. These results show that fundamental transitions to primitive cooperation can readily occur in bacteria.