Phage O4 of Pseudomonas aeruginosa was previously visualized as a short-tailed virus using a transmission electron microscope. In this work, the O4 genome was characterized to be a linear dsDNA molecule comprising 50509 bp with 76 predicted genes located in five clusters. Mass spectrometry showed that the O4 virion contains 6 putative structural proteins, 2 putative enzymes, and 7 hypothetical proteins. By analyzing a Tn5G transposon mutation library, eight genes, wbpR, wbpV, wbpO, wbpT, wbpS, wbpL, galU, and wzy, were identified and confirmed responsible for the phage-resistant phenotype; all of them are related to the synthesis of O-specific antigen (OSA) of lipopolysaccharide (LPS), indicating that OSA is the receptor for the adsorption of phage O4. Comparative genomic analysis revealed that the phage O4 genome shares little similarity to any known podovirus, indicating that phage O4 is classifiable as a novel member of the Podoviridae family.