Influenza vaccination is the primary approach to prevent influenza annually. WHO/CDC recommendations prioritize vaccinations mainly on the basis of age and co-morbidities, but have never considered influenza infection history of individuals for vaccination targeting. We evaluated such influenza vaccination policies through small-world contact networks simulations. Further, to verify our findings we analyzed, independently, large-scale empirical data of influenza diagnosis from the two largest Health Maintenance Organizations in Israel, together covering more than 74% of the Israeli population. These longitudinal individual-level data include about nine million cases of influenza diagnosed over a decade. Through contact network epidemiology simulations, we found that individuals previously infected with influenza have a disproportionate probability of being highly connected within networks and transmitting to others. Therefore, we showed that prioritizing those previously infected for vaccination would be more effective than a random vaccination policy in reducing infection. The effectiveness of such a policy is robust over a range of epidemiological assumptions, including cross-reactivity between influenza strains conferring partial protection as high as 55%. Empirically, our analysis of the medical records confirms that in every age group, case definition for influenza, clinical diagnosis, and year tested, patients infected in the year prior had a substantially higher risk of becoming infected in the subsequent year. Accordingly, considering individual infection history in targeting and promoting influenza vaccination is predicted to be a highly effective supplement to the current policy. Our approach can also be generalized for other infectious disease, computer viruses, or ecological networks.