Characterizing virus-host relationships is critical for understanding the impact of a virus on an ecosystem, but is challenging with existing techniques, particularly for uncultivable species. We present a general, cultivation-free approach for identifying phage-associated bacterial cells. Using PCR-activated cell sorting, we interrogate millions of individual bacteria for the presence of specific phage nucleic acids. If the nucleic acids are present, the bacteria are recovered via sorting and their genomes analyzed. This allows targeted recovery of all possible host species in a diverse population associated with a specific phage, and can be easily targeted to identify the hosts of different phages by modifying the PCR primers used for detection. Moreover, this technique allows quantification of free phage particles, as benchmarked against the “gold standard” of virus enumeration, the plaque assay.