Cooperative organisms evolve within socially diverse populations. In populations harboring both cooperators and cheaters, cooperators might adapt by evolving novel interactions with either social type or both. Diverse animal traits suppress selfish behaviors when cooperation is important for fitness, but the potential for prokaryotes to evolve such traits is unclear. We allowed a strain of the bacterium Myxococcus xanthus that is proficient at cooperative fruiting body development to evolve while repeatedly encountering a non-evolving developmental cheater. Evolving populations greatly increased their fitness in the presence of the cheater, both relative to their ancestor and in terms of absolute spore productivity. However, the same evolved lineages exhibited a net disadvantage to the ancestor in the cheater's absence. Evolving populations reversed a large ancestral disadvantage to the cheater into competitive superiority and also evolved to strongly suppress cheater productivity. Moreover, in three-party mixes with the cheater, evolved populations enhanced their ancestor's productivity relative to mixes of only the ancestor and cheater. Thus, our evolved populations function as selfish police that inhibit cheaters, both to their own advantage and to the benefit of others as well. Cheater suppression was general across multiple unfamiliar cheaters but was more pronounced against the evolutionarily familiar cheater. Also, evolution generated three new mutually beneficial relationships, including complementary defect rescue between evolved cells and the selection-regime cheater. The rapid evolution of cheater suppression documented here suggests that coevolving social strategies within natural populations of prokaryotes are more diverse and complex than previously appreciated.