We report the complete genome sequence of the phage BUCT-3589, infecting multidrug-resistant Klebsiella pneumoniae 3589. It is a new member of the genus Przondovirus in the family Autographiviridae and possesses a double-stranded DNA (dsDNA) genome of 40,757 bp with 53.13% GC content. The genome sequence will support its use as a therapeutic agent.