The inference of population dynamics from molecular sequence data is becoming an important new method for the surveillance of infectious diseases. Here, we examine how heterogeneity in contact shapes the genealogies of parasitic agents. Using extensive simulations, we find that contact heterogeneity can have a strong effect on how the structure of genealogies reflects epidemiologically relevant quantities such as the proportion of a population that is infected. Comparing the simulations to BEAST reconstructions, we also find that contact heterogeneity can increase the number of sequence isolates required to estimate these quantities over the course of an epidemic. Our results suggest that data about contact-network structure will be required in addition to sequence data for accurate estimation of a parasitic agent's genealogy. We conclude that network models will be important for progress in this area.