Malaria has never been endemic in New Zealand, and all cases have been diagnosed in international travelers. In this paper, we describe malaria cases reported from 1997 to 2009 and discuss epidemiological changes compared to a previous report from 1980 to 1992. From 1997 to 2009, 666 malaria infections were reported, with 410 cases (61.6%) in travelers aged 20-39 and 133 (20%) in military personnel. Infections were caused by Plasmodium vivax in 436 cases (72.7%) and Plasmodium falciparum in 163 (27.2%). In the 533 civilians, common countries of infection were Papua New Guinea (24.4%), India (18.6%), the Solomon Islands (8.8%), and Indonesia (6.1%). Most common regions of malaria acquisition for civilians were Papua New Guinea and Western Pacific (39.8%), Africa (24.7%), Indian subcontinent (19.5%), and Southeast Asia (13.6%). Compared to a previous report of malaria in New Zealand from 1980 to 1992, regions of malaria acquisition have changed significantly, with a lower percentage of cases acquired from Papua New Guinea and Western Pacific (from 59.2% to 39.3%), and a higher percentage from Africa (from 8.6% to 21.3%). The ethnic groups affected also differ significantly between the two surveillance periods, with a reduction in the percentage of cases reported in Caucasians (from 80.8 to 45.9%) and an increase in cases in Indians (from 7.0 to 15.7%), Papua New Guineans and Pacific Islanders (from 5.2 to 16.9%), other Asians (from 2.3 to 5.6%), and Africans (from 0 to 8.5%). Common locations of malaria infection have evolved over time and probably reflect changing travel patterns of New Zealanders and the origins of visitors and immigrants. Therefore, local surveillance is important for informing pretravel advice by identifying vulnerable groups and common destinations for malaria infection, so that special attention on malaria prevention can be focused on travelers who are at highest risk. Ongoing surveillance is also essential for monitoring the evolving epidemiology of imported malaria over time.