The genus Klebsiella is a significant contributor to bacterial infections in humans and is known to have a diverse environmental presence with many species and serotypes. Antimicrobial resistance (AMR) is of growing concern, with AMR strains from livestock and waterways potentially spilling over into community settings. Information regarding environmental drug-resistant Klebsiella is limited, with a focus on this knowledge gap increasing in urgency to facilitate efforts to track and control the spread of environmentally acquired Klebsiella infections. Bacteriophages hold the potential for controlling Klebsiella strains, both in the context of infections and environmental reservoirs. These viruses are found in the same niches as their bacteria prey, including waterway environments. Waterway samples thus provide a potential and untapped source of environmental Klebsiella-targeting viruses. In this study, water samples from across the Melbourne catchment region were collected and processed using a Klebsiella selective agar to isolate environmental strains of the bacterium. These strains were, in turn, used to isolate bacteriophage from the same water samples. Whole genome sequencing and phenotypic tests were used to classify the species of these Klebsiella strains and to characterize the protein structural features of the phages. This survey confirms the presence of Klebsiella bacteria and bacteriophages in Melbourne’s waterways and opens the way to understanding how AMR can be both potentiated and attenuated by environmental bacterium-bacteriophage relationships. Further work will evaluate the interaction mechanisms between phage proteins and their Klebsiella outer membrane receptors.