Background: Border malaria in the Greater Mekong region of Southeast Asia poses a serious threat to the health of the ethnic minority populations of the region. Traditionally thought to be caused primarily by the malaria parasites Plasmodium falciparum and Plasmodium vivax, recently a zoonotic parasite, Plasmodium knowlesi, has been identified in some countries of the region. The presence of this parasite poses a challenge to malaria control programmes, as it is maintained in a zoonotic reservoir of forest-dwelling macaque monkeys. Methods: A cross-sectional malaria parasite species prevalence survey was conducted along the Laos-Vietnam border in the central part of the two countries. Human blood samples were collected from Savannakhet in Laos and Quang Tri in Vietnam between August and October 2010 and assayed for the presence of human malaria parasite species and P. knowlesi. A PCR targeting the 18S small subunit ribosomal RNA gene and circumsporozoite protein gene was used for Plasmodium species identification. Results: Nine cases of P. knowlesi were detected by PCR in blood samples from the Laos side and three from the Vietnam side. All P. knowlesi infections were found in co-infection with P. vivax, with some triple infections of P. knowlesi, P. vivax and P. falciparum detected in Laos. Phylogenetic analysis of these parasites suggests that P. knowlesi is circulating in the Laos-Vietnam border region. Conclusion: This report shows that P. knowlesi is transmited on both sides of the Vietnam-Laos border. Continued monitoring of the range and prevalence of P. knowlesi on both the sides of Laos-Vietnam border is of importance to the National Malaria Control Programmes of both countries.