To estimate malaria rates in association with birth country, we analyzed routine surveillance data for US military members. During 2002-2010, rates were 44× higher for those born in western Africa than for those born in the United States. Loss of natural immunity renders persons susceptible when visiting birth countries. Pretravel chemoprophylaxis should be emphasized.