Phylogenetic trees are typically constructed using genetic and genomic data, and provide robust evolutionary relationships of species from the genomic point of view. We present an application of network motif mining and analysis of metabolic pathways that when used in combination with phylogenetic trees can provide a more complete picture of evolution. By using distributions of three-node motifs as a proxy for metabolic similarity, we analyze the ancestral origin of Eukaryotic organelles from the metabolic point of view to illustrate the application of our motif mining and analysis network approach. Our analysis suggests that the hypothesis of an early proto-Eukaryote could be valid. It also suggests that a δ- or ϵ-Proteobacteria may have been the endosymbiotic partner that gave rise to modern mitochondria. Our evolutionary analysis needs to be extended by building metabolic network reconstructions of species from the phylum Crenarchaeota, which is considered to be a possible archaeal ancestor of the eukaryotic cell. In this paper, we also propose a methodology for constructing phylogenetic trees that incorporates metabolic network signatures to identify regions of genomically-estimated phylogenies that may be spurious. We find that results generated from our approach are consistent with a parallel phylogenetic analysis using the method of feature frequency profiles. (C) 2014 Elsevier Ltd. All rights reserved.