Helicobacter pylori causes peptic ulcers and gastric cancer, which lead to significantly higher morbidity in Japan than elsewhere in the world. As bacteriophage (phage) and host bacteria coevolve, the study of H. pylori phages is important to extend understanding of the evolution and pathogenesis of H. pylori. Here we report two complete genome sequences of H. pylori phages KHP30 and KHP40, which were released spontaneously from the most pathogenic East Asian-type isolates from Japanese patients.