Melioidosis, infection caused by Burkholderia pseudomallei, is increasingly reported in Cambodia. We hypothesized that implementation of an enhanced sputum testing protocol in a provincial hospital diagnostic microbiology laboratory would increase detection of B. pseudomallei. We tested 241 sputum specimens that were deemed acceptable for culture, comparing culture in selective enrichment broth followed by sub-culture on Ashdown’s medium to standard culture methods. Two specimens (0.8%) were positive for B. pseudomallei using the enhanced protocol whereas one specimen (0.4%) was positive using standard methods. Given the low numbers of positive specimens, we could not conclusively determine the utility of the enhanced sputum testing protocol. However, the ramifications of identification of B. pseudomallei are substantial, and the benefit of the enhanced testing protocol may be more apparent in patients selected based on risk factors and clinical presentation. Promoting clinician awareness of the infection and encouraging utilization of diagnostic microbiology services are also likely to be important factors in facilitating identification of melioidosis.