The Military Health System (MHS), with 9.7 million beneficiaries, represents an enormous pool of potential travelers requiring malaria prevention measures. A systematic search of the MHS electronic pharmacy record was performed for prescriptions of atovaquone-proguanil (AP), chloroquine (CQ), doxycycline (DC), mefloquine (MQ), primaquine (PQ) to adult patients from 2007 through 2011. Over 1,000,000 were identified, including 161,341 primary prophylaxis prescriptions originating from civilian facilities. Military facility prescription volume rose from 50,128 (PQ < 1%, AP 4%, CQ 6%, DC 53%, MQ 36%) in 2007 to 166,649 (PQ < 1%, AP 3%, CQ < 1%, DC 94%, MQ 2%) in 2011. Mefloquine use diminished in all clinics over time. The majority of military facility prescriptions originated from primary care clinics (83%); primary care clinics predominantly and increasingly prescribed DC, whereas specialty travel clinics predominantly and increasingly prescribed AP. Prescribing patterns in the MHS varied by time, practice setting, beneficiary status, and provider specialty. These changes, including among non-active duty military patients, are temporally associated with policy changes intended for the active duty force.