In models of disease transmission on contact networks, the probability of exposure is determined by the connectivity (degree) of the individual (node). Thus, the most highly connected individuals in a contact network have both a higher probability of spreading infection through the population and a higher rate of exposure (susceptibility) through social contacts. As an epidemic sweeps through a population, this heterogeneity leads to systematic structural changes in the active portion of the network, removing immunized individuals who no longer participate in the chains of transmission. While the impact of network structure on the progression of an epidemic has been well studied, there has been relatively little work on network evolution during the course of an epidemic. We analytically investigate the impact of epidemic dynamics on the underlying host population structure and find that the structural evolution of the network varies with the original topology of the network and the contagiousness of the disease. We identify the mechanisms acting on the network topology to make them sparser, consider questions about the patterns of immunity that arise during disease outbreaks, and explore their impact on future epidemics and key public health policies.