Maternally transmitted symbionts can spread in host populations if they provide a fitness benefit to their hosts. Hamiltonella defensa, a bacterial endosymbiont of aphids, protects hosts against parasitoids but only occurs at moderate frequencies in most aphid populations. This suggests that harbouring this symbiont is also associated with costs, yet the nature of these costs has remained elusive. Here we demonstrate an important and clearly defined cost: reduced longevity. Experimental infections with six different isolates of H. defensa caused strongly reduced lifespans in two different clones of the black bean aphid, Aphis fabae, resulting in a significantly lower lifetime reproduction. However, the two aphid clones were unequally affected by the presence of H. defensa, and the magnitude of the longevity cost was further determined by genotype × genotype interactions between host and symbiont, which has important consequences for their coevolution.