As the most abundant microbes on Earth, novel bacteriophages (phages; bacteria-specific viruses) are readily isolated from environmental samples. However, it remains challenging to characterize phage–bacteria interactions, such as the host receptor(s) phages 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 (phages T6, T2, T4, and T7). INSeq screens were then used to identify genes involved during infection of six newly isolated coliphages. Results showed that candidate receptors could be successfully identified for the majority (five of six) of the phages; 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 phages, as well as usefulness of the method for exploring the evolution of broad versus narrow use of cellular receptors among phages in the biosphere.