Viruses control natural microbial communities. Identification of virus-host pairs relies either on their cultivation or on metagenomics and tentative assignment based on genomic signatures. Both approaches have severe drawbacks when aiming to target such pairs within the uncultured majority. Here we present an unambiguous way to assign viruses to hosts that does not rely on any previous information about either of them nor requires their cultivation. First, genomic contents of individual cells present in an environmental sample are retrieved by means of single-cell genomic technologies. Then, individual cell genomes are hybridized against a set of individual viral genomes from the same sample, previously immobilized on a microarray. Infected cells will yield positive hybridization as they carry viral genomes, which can be then sequenced and characterized. Using this method, we pinpoint viruses infecting the ubiquitous hyperhalophilic Nanohaloarchaeota, included in the so-called 'microbial dark matter' (the uncultured fraction of the microbial world).