Whilst many invertebrate taxa are haplodiploid, the factors underlying the evolution of haplodiploidy remain unresolved. We investigate theoretically whether haplodiploidy might evolve as an outcome of the co-evolution between maternally inherited endosymbionts and their hosts. First, we substantially extend a recently developed model that involves maternally inherited endosymbionts that kill male offspring by eliminating the paternal genome. We also put forward a new hypothesis and develop a model that involves bacteria that induce cytoplasmic incompatibility (CI). Based on these models, we explore the co-evolutionary events that might occur between hosts and symbionts. We find that both with male-killers and CI-inducing endosymbionts, the hosts are likely to develop increased viability of haploid males, which can be considered a preadaptation to haplodiploidy. In addition, populations with haploidizing male-killers can in some cases evolve directly towards a genetic system of paternal genome elimination, a special form of haplodiploidy. These results are combined with consideration of mechanism and ecology to appraise the likelihood of male-killers and CI inducing bacteria being involved in the evolution of haplodiploidy.