Paenibacillus polymyxa is an agriculturally important plant growth promoting rhizobacterium (PGPR). Many Paenibacillus species are known to be engaged in complex bacteria-bacteria and bacteria-host interactions, which in other bacteria were shown to necessitate quorum sensing communication, but to date no quorum sensing systems have been described in Paenibacillus. Here we show that the type strain P. polymyxa ATCC 842 encodes at least 16 peptide-based communication systems. Each of these systems comprises a pro-peptide that is secreted to the growth medium and further processed to generate a mature short peptide. Each peptide has a cognate intracellular receptor of the RRNPP family, and we show that external addition of P. polymyxa communication peptides to the medium leads to reprogramming of the transcriptional response. We found that these quorum sensing systems are conserved across hundreds of species belonging to the Paenibacillaceae family, with some species encoding more than 25 different peptide-receptor pairs, representing a record number of quorum sensing systems encoded in a single genome.