Clinical presentations of melioidosis, caused by Burkholderia pseudomallei are protean, but the mechanisms underlying development of the different forms of disease remain poorly understood. In murine melioidosis, the level of virulence of B. pseudomallei is important in disease pathogenesis and progression. In this study, we used B. pseudomallei-susceptible BALB/c mice to determine the virulence of a library of clinical and environmental B. pseudomallei isolates from Australia and Papua New Guinea. Among 42 non-arabinose-assimilating (ara-) isolates, LD50 ranged from 10 to > 106 CFU. There were numerous correlations between virulence and disease presentation in patients; however, this was not a consistent observation. Virulence did not correlate with isolate origin (i.e. clinical vs environmental), since numerous ara- environmental isolates were highly virulent. The least virulent isolate was a soil isolate from Papua New Guinea, which was arabinose assimilating (ara+). Stability of B. pseudomallei virulence was investigated by in vivo passage of isolates through mice and repetitive in vitro subculture. Virulence increased following in vivo exposure in only one of eight isolates tested. In vitro subculture on ferric citrate-containing medium caused attenuation of virulence, and this correlated with changes in colony morphology. Pulsed-field gel electrophoresis and randomly amplified polymorphic DNA typing demonstrated that selected epidemiologically related isolates that had variable clinical outcomes and different in vivo virulence were clonal strains. No molecular changes were observed in isolates after in vivo or in vitro exposure despite changes in virulence. These results indicate that virulence of selected B. pseudomallei isolates is variable, being dependent on factors such as iron bioavailability. They also support the importance of other variables such as inoculum size and host risk factors in determining the clinical severity of melioidosis.