Objective: Epidemiological surveillance of malaria in France is based on a hospital laboratory sentinel surveillance network. There is no comprehensive population surveillance. The objective of this study was to assess the ability of the French National Health Insurance Information System to support nationwide malaria surveillance in continental France. Materials and methods: A case identification algorithm was built in a 2-step process. First, inclusion rules giving priority to sensitivity were defined. Then, based on data description, exclusion rules to increase specificity were applied. To validate our results, we compared them to data from the French National Reference Center for Malaria on case counts, distribution within subgroups, and disease onset date trends. Results: We built a reusable automatized tool. From July 1, 2013, to June 30, 2014, we identified 4077 incident malaria cases that occurred in continental France. Our algorithm provided data for hospitalized patients, patients treated by private physicians, and outpatients for the entire population. Our results were similar to those of the National Reference Center for Malaria for each of the outcome criteria. Discussion: We provided a reliable algorithm for implementing epidemiological surveillance of malaria based on the French National Health Insurance Information System. Our method allowed us to work on the entire population living in continental France, including subpopulations poorly covered by existing surveillance methods. Conclusion: Traditional epidemiological surveillance and the approach presented in this paper are complementary, but a formal validation framework for case identification algorithms is necessary.