Environmental changes can dramatically alter the composition of complex communities and drive evolutionary change among community members. The vertebrate gut microbiota—the diverse community of microorganisms that reside in the gastrointestinal tract—is an ideal system to study simultaneous ecological changes and adaptive evolution across all community members in a changing environment. This is due to short generation times, tractability both in vitro and in vivo, and advances in metagenomic sequencing that capture both community composition and metagenomic content from a single biological sample. A common environmental shift experienced by gut microbiota is a change in host diet. In mammals, the gut microbiota are dependent upon host diet for nutrients and the host is dependent upon the microbiota for proper digestion and overall fitness. Rapid shifts in gut microbial composition following a change in host diet are well-documented; however, the extent to which the gut microbiota adapt to change in host diet is not yet understood. In Chapters 1 and 2, I develop and validate methods that can be used to study gut microbial evolution. Chapter 1 demonstrates that gut microbiota from diverse vertebrates, including house mice (Mus musculus domesticus), are culturable. Culturing recovers many bacterial species that are not captured by culture-independent sequencing, and can provide high-quality isolate genomes and live cultures for manipulative experiments. In Chapter 2, I validate Hackflex, a low-cost library preparation method, for metagenomic sequencing of mouse gut microbial communities. Hackflex yields libraries that are comparable to standard Illumina library preparation methods, but at 1/14th the cost. This greatly expands access to high-throughput metagenomic sequencing. Lastly, in Chapter 3, I developed experimental and bioinformatic tools to track longitudinal changes in allele frequency across all prevalent species in the mouse gut microbiome in response to a shift to a high-fat diet. I found that nearly all members of the gut microbiota adapted, representing a previously unstudied aspect of gut microbial variation. These findings highlight that rapid adaptation, alongside ecological turnover, fundamentally shapes gut microbial communities in response to environmental changes. Collectively, this dissertation provides a framework for investigating evolutionary dynamics within complex microbial communities.