Melioidosis is a disease of significant public health importance that is being increasingly recognized globally. The majority of cases arise through direct percutaneous exposure to its etiological agent, Burkholderia pseudomallei. In the Lao People’s Democratic Republic (Laos), the presence and environmental distribution of B. pseudomallei are not well characterized, though recent epidemiological surveys of the bacterium have indicated that B. pseudomallei is widespread throughout the environment in the center and south of the country and that rivers can act as carriers and potential sentinels for the bacterium. The spatial and genetic distribution of B. pseudomallei strains within Vientiane Capital, where the majority of cases diagnosed to date have originated, remains an important knowledge gap. We sampled surface runoff from drain catchment areas throughout urban Vientiane to determine the presence and local population structure of the bacterium. B. pseudomallei was detected in drainage areas throughout the capital, indicating that it is widespread in the environment and that exposure rates in urban Vientiane are likely higher than previously thought. Whole-genome comparative analysis demonstrated that Lao B. pseudomallei isolates are highly genetically diverse, suggesting that the bacterium is well established and not a recent introduction. Despite the wide genome diversity, one environmental survey isolate was highly genetically related to a Lao melioidosis patient isolate collected 13 years prior to the study. Knowledge gained from this study will augment understanding of B. pseudomallei phylogeography in Asia and enhance public health awareness and future implementation of infection control measures within Laos.