We present the complete genome sequences of four phages that infect Paenibacillus larvae, the causative agent of American foulbrood disease in honeybees. The phages were isolated from beehives and beeswax products from Las Vegas, Nevada. The genomes are 50 to 55 kbp long and use the "direct terminal repeats" DNA-packaging strategy.