Coevolution between different biological entities is considered an important evolutionary mechanism at all levels of biological organization. Here we provide evidence for coevolution of a yeast killer strain (K) carrying cytoplasmic dsRNA viruses coding for anti-competitor toxins and an isogenic toxin-sensitive strain (S) during 500 generations of laboratory propagation. Signatures of coevolution developed at two levels. One of them was coadaptation of K and S. Killing ability of K first increased quickly and was followed by the rapid invasion of toxin-resistant mutants derived from S, after which killing ability declined. High killing ability was shown to be advantageous when sensitive cells were present but costly when they were absent. Toxin resistance evolved via a two-step process, involving the fitness-enhancing loss of one chromosome followed by selection of a recessive resistant mutation on the haploid chromosome. The other level of coevolution occurred between cell and killer virus. By swapping the killer viruses between ancestral and evolved strains, we could demonstrate that changes observed in both host and virus were beneficial only when combined, suggesting that they involved reciprocal changes. Together, our results show that the yeast killer system shows a remarkable potential for rapid multiple-level coevolution.