We sequenced the genomes of recently discovered Paenibacillus melissococcoides (CCOS 2000) and of the type strains of closely related P. thiaminolyticus (DSM 7262) and P. dendritiformis (LMG 21716). The three genomes set the basis to unambiguous diagnostic of these honey bee associated Paenibacillus bacteria.