As the most abundant microbes on earth, novel bacteriophage (phage; bacteria-specific viruses) are readily isolated from environmental samples. However, it remains challenging to characterize phage-bacteria interactions, such as the host receptor(s) phage bind to initiate infection. Here, we tested whether transposon insertion sequencing, INSeq, could be used to identify bacterial genes involved in phage binding. As proof of concept, results showed that INSeq screens successfully identified genes encoding known receptors for previously characterized viruses of Escherichia coli (phage T6, T2, T4 and T7). INSeq screens were then used to identify genes involved during infection of six newly isolated coliphage. Results showed that candidate receptors could be successfully identified for the majority (five of six) of the phage; furthermore, genes encoding the phage receptor(s) were the top hit(s) in the analyses of the successful screens. INSeq screens provide a generally useful method for high-throughput discovery of phage receptors. We discuss limitations of our approach when examining uncharacterized phage, as well as usefulness of the method for exploring the evolution of broad versus narrow use of cellular receptors among phage in the biosphere.