Brown-headed Cowbirds (Molothrus ater) are the most widespread avian brood parasite in North America, laying their eggs in the nests of approximately 250 host species that raise the cowbird nestlings as their own. It is currently unknown how these heterospecific hosts influence the cowbird gut microbiota relative to other factors, such as the local environment and genetics. We test a Nature Hypothesis (positing the importance of cowbird genetics) and a Nurture Hypothesis (where the host parents are most influential to cowbird gut microbiota) using the V6 region of 16S rRNA as a microbial fingerprint of the gut from 32 cowbird samples and 16 potential hosts from nine species. We test additional hypotheses regarding the influence of the local environment and age of the birds. We found no evidence for the Nature Hypothesis and little support for the Nurture Hypothesis. Cowbird gut microbiota did not form a clade, but neither did members of the host species. Rather, the physical location, diet and age of the bird, whether cowbird or host, were the most significant categorical variables. Thus, passerine gut microbiota may be most strongly influenced by environmental factors. To put this variation in a broader context, we compared the bird data to a fecal microbiota dataset of 38 mammal species and 22 insect species. Insects were always the most variable; on some axes, we found more variation within cowbirds than across all mammals. Taken together, passerine gut microbiota may be more variable and environmentally determined than other taxonomic groups examined to date.