Abstract Background Malaria remains a critical public health problem in Southeast Asia despite intensive containment efforts. The continued spread of multi-drug-resistant Plasmodium falciparum has led to calls for malaria elimination on the Thai-Cambodian border. However, the optimal approach to elimination in difficult-to-reach border populations, such as the Military, remains unclear. Methods/design A two-arm, cluster-randomized controlled, open-label pilot study is being conducted in military personnel and their families at focal endemic areas on the Thai-Cambodian border. The primary objective is to compare the effectiveness of monthly malaria prophylaxis (MMP) with dihydroartemisinin-piperaquine and weekly primaquine for 12 weeks compared with focused screening and treating (FSAT) following current Cambodian national treatment guidelines. Eight separate military encampments, making up approximately 1000 military personnel and their families, undergo randomization to the MMP or FSAT intervention for 3 months, with an additional 3 months’ follow-up. In addition, each treatment cluster of military personnel and civilians is also randomly assigned to receive either permethrin- or sham (water)-treated clothing in single-blind fashion. The primary endpoint is risk reduction for malaria infection in geographically distinct military encampments based on their treatment strategy. Monthly malaria screening in both arms is done via microscopy, PCR, and rapid diagnostic testing to compare both the accuracy and cost-effectiveness of diagnostic modalities to detect asymptomatic infection. Universal glucose-6-phosphate dehydrogenase (G6PD) deficiency screening is done at entry, comparing the results from a commercially available rapid diagnostic test, the fluorescence spot test, and quantitative testing for accuracy and cost-effectiveness. The comparative safety of the interventions chosen is also being evaluated. Discussion Despite the apparent urgency, the key operational elements of proposed malaria elimination strategies in Southeast Asian mobile and migrant populations, including the Military, have yet to be rigorously tested in a well-controlled clinical study. Here, we present a protocol for the primary evaluation of two treatment paradigms – monthly malaria prophylaxis and focused screening and treatment – to achieve malaria elimination in a Cambodian military population. We will also assess the feasibility and incremental benefit of outdoor-biting vector intervention – permethrin-treated clothing. In the process, we aim to define the cost-effectiveness of the inputs required for success including a responsive information system, skilled human resource and laboratory infrastructure requirements, and quality management. Despite being a relatively low transmission area, the complexities of multi-drug-resistant malaria and the movement of vulnerable populations require an approach that is not only technically sound, but simple enough to be achievable. Trial registration ClinicalTrials.gov, ID: NCT02653898 . Registered on 13 January 2016.