A comprehensive model of evolution requires an understanding of the relationship between selection at the molecular and phenotypic level. We investigate this in Strepsiptera, an order of endoparasitic insects whose evolutionary biology is poorly studied. We present the first molecular phylogeny of Strepsiptera, and use this as a framework to investigate the association between parasitism and molecular evolution. We find evidence of a significant burst in the rate of molecular evolution in the early history of Strepsiptera. The evolution of morphological traits linked to parasitism is significantly correlated with the pattern in molecular rate. The correlated burst in genotypic-phenotypic evolution precedes the main phase of strepsipteran diversification, which is characterised by the return to a low and even molecular rate, and a period of relative morphological stability. These findings suggest that the transition to endoparasitism led to relaxation of selective constraint in the strepsipteran genome. Our results indicate that a parasitic lifestyle can affect the rate of molecular evolution, although other causal life-history traits correlated with parasitism may also play an important role.