Bacterial species belonging to the genus Burkholderia have been repeatedly reported to be associated with fungi but the extent and specificity of these associations in soils remain undetermined. To assess whether associations between Burkholderia and fungi are widespread in soils, we performed a co-occurrence analysis in an intercontinental soil sample collection. This revealed that Burkholderia significantly co-occurred with a wide range of fungi. To analyse the molecular basis of the interaction, we selected two model fungi frequently co-occurring with Burkholderia, Alternaria alternata and Fusarium solani, and analysed the proteome changes caused by cultivation with either fungus in the widespread soil inhabitant B. glathei, whose genome we sequenced. Co-cultivation with both fungi led to very similar changes in the B. glathei proteome. Our results indicate that B. glathei significantly benefits from the interaction, which is exemplified by a lower abundance of several starvation factors that were highly expressed in pure culture. However, co-cultivation also gave rise to stress factors, as indicated by the increased expression of multidrug efflux pumps and proteins involved in oxidative stress response. Our data suggest that the ability of Burkholderia to establish a close association with fungi mainly lies in the capacities to utilize fungal-secreted metabolites and to overcome fungal defense mechanisms. This work indicates that beneficial interactions with fungi might contribute to the survival strategy of Burkholderia species in environments with sub-optimal conditions, including acidic soils.