Many biological networks can maintain their function against single gene loss. However, the evolutionary mechanisms responsible for such robustness remain unclear. Here, we demonstrate that antagonistic host-parasite interactions can act as a selective pressure driving the emergence of robustness against gene loss. Using a model of host signaling networks and simulating their coevolution with parasites that interfere with network function, we find that networks evolve both redundancy and specific architectures that allow them to maintain their response despite removal of proteins. We show that when the parasite pressure is removed, subsequent evolution can lead to loss of redundancy while architecture-based robustness is retained. Contrary to intuition, increased parasite virulence hampers evolution of robustness by limiting the generation of population level diversity in the host. However, when robustness emerges under high virulence, it tends to be stronger. These findings predict an increased presence of robustness mechanisms in biological networks operating under parasite interference. Conversely, the presence of such mechanisms could indicate current or past parasite interference.