Bacteriophages, or phages, utilise specialised receptor binding proteins (RBPs) to recognise their target bacterial prey. Understanding the sequence and structural features of these proteins can provide insights into their specific receptor interactions. We have isolated and characterised several phages that infect the important human pathogen Klebsiella pneumoniae. We identified highly related Klebsiella-targeting phages that exhibit specific host tropisms, such that the presence or absence of capsular polysaccharide (CPS) is an essential factor in determining phage sensitivity or resistance respectively. We show that the acapsular targeting phages instead target lipopolysaccharides (LPS) on the cell surface rather than CPS. Sequence analysis of each of the respective RBPs showed conservation of the N-terminal domain which is essential for anchoring the RBPs to the baseplate of the virion. Conversely, the C-terminal domains are unique, both in sequence and structure, which function either to hydrolyse the protective CPS barrier or to recognise LPS on the bacterial cell surface. This work has identified examples of mosaic RBPs that have formed as a result of natural phage evolution and provides a native protein scaffold for engineering of designer synthetic phages with different host targeting mechanisms for more effective phage-based applications.