Recently, two strains related to Burkholderia terrae, denoted BS001 and BS110, were shown to be strongly interactive with the soil fungus Lyophyllum sp. strain Karsten, forming a biofilm around the L. sp. strain Karsten hyphae and migrating along growing hyphae in soil. Here, we extend the findings obtained with strains BS001 and BS110 and show that the migratory ability with extending fungal hyphae is actually distributed among four Burkholderia phylotypes obtained from a range of soils with different characteristics. The majority of the migrating strains fell into a rather narrow group related to the original strain B. terrae BS001, but others fell in groups related to B. terricola, B. xenovorans and B. phytofirmans. To obtain these novel strains, bacterial inocula were obtained as cell extracts from eight soils and subsequently introduced into four (sandy acidic) pre-sterilized soils in microcosms which were then colonized by L. sp. strain Karsten or kept without this fungus. After 2 weeks of incubation, the soil microcosms were sampled at the migration front and samples were plated on semi-selective PCAT agar medium next to R2A medium. A total of 19 strains that had revealed the capability to comigrate with the fungus were obtained from this set-up, whereas four other strains were found in previous field work. Strains were analysed by BOX-PCR, pulsed-field gel electrophoresis, partial 16S rRNA gene similarity, metabolic profiling using BIOLOG and for the presence of a type three secretion system (TTSS). All strains belonged to the genus Burkholderia. Following this, selected strains were shown to be capable of single-strain comigration with the L. sp. strain Karsten hyphae through different soils. However, their avidity to do so differed across soils. For their ecological competence, the four different comigrating phylotypes may rely on their capacities to migrate as well as consume fungal-released compounds.