Exposure of Anopheles gambiae mosquitoes to Plasmodium infection enhances the ability of their immune system to respond to subsequent infections. However, the molecular mechanism that allows the insect innate immune system to 'remember' a previous encounter with a pathogen has not been established. Challenged mosquitoes constitutively release a soluble haemocyte differentiation factor into their haemolymph that, when transferred into Naive mosquitoes, also induces priming. Here we show that this factor consists of a Lipoxin/Lipocalin complex. We demonstrate that innate immune priming in mosquitoes involves a persistent increase in expression of Evokin (a lipid carrier of the lipocalin family), and in their ability to convert arachidonic acid to lipoxins, predominantly Lipoxin A4. Plasmodium ookinete midgut invasion triggers immune priming by inducing the release of a mosquito lipoxin/lipocalin complex.