Decreasing the number of people who must be vaccinated to immunize a community against an infectious disease could both save resources and decrease outbreak sizes. A key to reaching such a lower threshold of immunization is to find and vaccinate people who, through their behavior, are more likely than average to become infected and to spread the disease further. Fortunately, the very behavior that makes these people important to vaccinate can help us to localize them. Earlier studies have shown that one can use previous contacts to find people that are central in static contact networks. However, real contact patterns are not static. In this paper, we investigate if there is additional information in the temporal contact structure for vaccination protocols to exploit. We answer this affirmative by proposing two immunization methods that exploit temporal correlations and showing that these methods outperform a benchmark static-network protocol in four empirical contact datasets under various epidemic scenarios. Both methods rely only on obtainable, local information, and can be implemented in practice. For the datasets directly related to contact patterns of potential disease spreading ( of sexually-transmitted and nosocomial infections respectively), the most efficient protocol is to sample people at random and vaccinate their latest contacts. The network datasets are temporal, which enables us to make more realistic evaluations than earlier studies-we use only information about the past for the purpose of vaccination, and about the future to simulate disease outbreaks. Using analytically tractable models, we identify two temporal structures that explain how the protocols earn their efficiency in the empirical data. This paper is a first step towards real vaccination protocols that exploit temporal-network structure-future work is needed both to characterize the structure of real contact sequences and to devise immunization methods that exploit these.