Organisms are in constant contact with both harmful and benign microbes. Evolutionary approaches can enrich our understanding of these interactions and provide insight into their dynamics through time and across space. Here, I present an evolutionary study of the fruit fly Drosophila melanogaster to investigate the multiple ways microbes and parasites have shaped the evolution of this model host. Chapter 1 explores D. melanogaster's interactions with its gut bacteria. Using 37 inbred fly lines, I found that fly genotypes differ in their amount of gut bacteria. Gut microbiome size correlated with other phenotypes assayed in these lines, suggesting that commensal bacterial load may influence aspects of fly fitness-from nutrient allocation to mating behavior. While the fly only transiently interacts with these gut microbes, it maintains a lifelong relationship with the endosymbiont Wolbachia pipientis. In Chapter 2, I present a phylogenetic analysis of 65 globally distributed Wolbachia and mitochondrial genomes. Wolbachia infections showed strong geographic structuring and no evidence of horizontal transmission or recombination. Demonstrating a tight evolutionary relationship between host and bacteria, I determined that all extant Wolbachia infections in D. melanogaster are monophyletic, coalescing to a single infected individual approximately 2200 years ago. Chapter 3 more broadly considers all classes of parasites, pathogens, and commensals. Leveraging our extensive knowledge of D. melanogaster gene function, I infer global variation in pathogen-induced selection pressures, and find that immune processes differ in extent and route of local adaptation. Parasitoid wasps and viruses have most profoundly impacted the recent evolution of D. melanogaster immune genes, but the underlying genetic architectures of these adaptive events differ. Genes also experience intra-cellular selection pressures. In Chapter 4, I investigate how these intra-organismal forces shape immune gene adaptation by calculating metrics of network position and pleiotropy for each D. melanogaster immune gene. I found that protein-protein interactions constrain a gene's adaptive potential, but that this constraint is most apparent in processes that experience strong directional selection. Taken together, these studies provide a more complete picture of the multi-faceted nature of host-microbe interactions, and establish an expanded framework for future research in Drosophila immunity.