Insects typically host substantial microbial communities (the 'microbiome') that can serve as a vital source of nutrients and also acts as a modulator of immune function. While recent studies have shown that diet is an important influence on the gut microbiome, very little is known about the dynamics underpinning microbial acquisition from natural food sources. Here, we addressed this gap by comparing the microbiome of larvae of the polyphagous fruit fly Bactrocera tryoni ('Queensland fruit fly') that were collected from five different fruit types (sapodilla [from two different localities], hog plum, pomegranate, green apple, and quince) from North-east to South-east Australia. Using Next-Generation Sequencing on the Illumina MiSeq platform, we addressed two questions: (1) what bacterial communities are available to B. tryoni larvae from different host fruit; and (2) how does the microbiome vary between B. tryoni larvae and its host fruit? The abundant bacterial taxa were similar for B. tryoni larvae from different fruit despite significant differences in the overall microbial community compositions. Our study suggests that the bacterial community structure of B. tryoni larvae is related less to the host fruit (diet) microbiome and more to vertical transfer of the microbiome during egg laying. Our findings also suggest that geographic location may play a quite limited role in structuring of larval microbiomes. This is the first study to use Next-Generation Sequencing to analyze the microbiome of B. tryoni larvae together with the host fruit, an approach that has enabled greatly increased resolution of relationships between the insect's microbiome and that of the surrounding host tissues.