Heterologous immunity, or protection by one invading organism against another across phylogenetic divides, has been recognised for decades. It was initially thought to operate largely through enhancement of phagocytosis, but this explanation became untenable when it was realised it worked extremely well against intraerythrocytic protozoa and killed them while they were free in the circulation. Clearly a soluble mediator was called for. This review summarises the logic that arose from this observation, which led to a wider appreciation of the roles of pro-inflammatory cytokines, and then nitric oxide, in the host's response against invaders, as well as the ability of these mediators to harm the host itself if they are generated too enthusiastically. This has led to a discernable pattern across heterologous immunity as a whole, and its lessons influence a range of areas, including vaccine development.