Klebsiella pneumoniae is one of the most significant nosocomial pathogens and an important cause of human infections worldwide. The microorganism is capable of producing different capsular polysaccharides (CPSs), which are the primary receptors for capsule-specific K. pneumoniae bacteriophages encoding tailspike proteins (TSPs) with polysaccharide-degrading activity. In this study, the novel virulent Przondovirus phage Adeo was isolated and characterized. The phage was able to infect K. pneumoniae strain with a K39 capsular polysaccharide structure. The morphology, biological properties, stability, and genomic organization of Adeo were studied. Comparative genomic and phylogenetic analyses were performed to establish the relationship between the phage and other bacterial viruses. The gene encoding TSP Adeo_gp48 was identified and cloned. Recombinant depolymerase lacking the N-terminal part was expressed, purified, and formed an opaque zone of CPS depolymerization on the K39 K. pneumoniae bacterial lawns. The structural and phylogenetic similarities of Adeo’s TSP to other phage-encoded depolymerases were discussed.