Inferring transcriptional regulatory networks from gene-expression data remains a challenging problem, in part because of the noisy nature of the data and the lack of strong network models. Time-series expression data have shown promise and recent work by Babu on the evolution of regulatory networks in E. coli and S. cerevisiae opened another avenue of investigation. In this paper we take the evolutionary approach one step further. We conjecture that established phylogenetic relationships among a group of related organisms can be used to improve the inference of regulatory networks for these organisms from expression data gathered under similar conditions. We develop an inference algorithm to take advantage of such information and present the results of simulations (including various tests to exclude confounding factors) that clearly show the added value of the phylogenetic information. Our algorithm and results offer support for our conjecture and indicate that gene-expression studies under identical conditions across a range of related organisms could yield significantly more accurate regulatory networks than single-organism studies.