Viral discovery is accelerating at an unprecedented rate due to continuing advances in culture-independent sequence-based analyses. One important facet of this discovery is identification of the hosts of these newly characterised uncultured viruses. To this end, we have developed a single cell viral tagging approach. Fluorescently labeled anonymous virions are allowed to adsorb to unlabeled anonymous bacterial host cells which are then individually sorted as virus-host pairs, followed by genome amplification and high throughput sequencing to establish the identities of both the host and attached virus(es). We show the application of this method in the human gut microbiome including cross-tagging of viruses and bacteria between subjects.