The study site located in the Mediterranean Sea was visited eight times in 2005 and 2006 to collect samples from the epipelagic (5 m), mesopelagic (200 m, 600 m), and bathypelagic (1,000 m, 2,000 m) zones. Randomly amplified polymorphic DNA PCR (RAPD-PCR) analysis was used to obtain fingerprints from microbial and viral size fractions using two different primers each. Depending on the primer used, the number of bands in the water column varied between 12 to 24 and 6 to 19 for the microbial size fraction and between 16 to 26 and 8 to 22 for the viral size fraction. The majority of sequences from the microbial fraction was related to Alphaproteobacteria, Cyanobacteria, Gammaproteobacteria, Firmicutes, and Eukaryota. Only 9% of sequences obtained from the viral fraction were of identifiable viral origin; however, 76% of sequences had no close relatives in the nr database of GenBank. Only 20.1% of complete phage genomes tested in silico resulted in potential RAPD-PCR products, and only 12% of these were targeted by both primers. Also, in silico analysis indicated that RAPD-PCR profiles obtained by the two different primers are largely representative of two different subsets of the viral community. Also, correlation analyses and Mantel tests indicate that the links between changes in the microbial and viral community were strongest in the bathypelagic. Thus, these results suggest a strong codevelopment of virus and host communities in deep waters. The data also indicate that virus communities in the bathypelagic zone can exhibit substantial temporal dynamics.