Melittobia, a polyphagous pupal parasitoid of many solitary bees and wasps, has a complex courtship display, the evolutionary history of which is poorly understood. The current phylogeny of this genus suggests the complexity of the courtship has increased over time. We test this hypothesis using Bayesian and Maximum likelihood techniques to construct a molecular phylogeny of Melittobia-the first for this genus using modern techniques--using two intergenic regions (Internal Transcribed Spacer regions 1 and 2) and Cytochrome Oxidase 1 (CO1), and reconstruct the ancestral state of each major node in the phylogeny for five behaviors coincidental to major shifts in display complexity. We show that species-groups identified solely on behavioral characters are reliable, although the relationships among groups are different than those previously hypothesized. We also show that behaviors traditionally used in the courtship studies do not support a hypothesis of increasing display complexity over time.