Author Summary From humans to social insects and bacteria, decision-making is often influenced by some form of collective signaling, be it quorum, information exchange, pledges or announcements. Here we investigate how such signaling systems evolve when collective action entails a public good, and how meanings co-evolve with individual choices, given Nature’s most prevalent states. We find a rich scenario, showing how natural selection is able to evolve a costly quorum signaling system that allows individuals to coordinate their action so as to provide the appropriate response to different states of Nature. We show that signaling robustly and selectively promotes cooperative collective action when coordinated action is most needed. In light of our results, and despite the complexity that collective action relying on quorum signaling may entail, it is not so surprising how signaling is a ubiquitous property of the living world.