This paper attempts to reconstruct the phylogeny of azoreductase enzyme from different organisms and compare it with the small subunit rRNA-based phylogeny of the organisms. The two phylogenies were found to be incongruent, indicating several events of lateral transfer of azoreductase gene between phylogenetically diverse organisms. However, the phylogenetic analysis methods have several limitations and a single method may not give the true pattern. Hence, it is necessary to corroborate the results with other complementary analysis tools. We used several tools to test our hypothesis of lateral transfer and found that it was supported not only by the analysis of the whole sequences, but also by the conserved motifs detected in these sequences. There were ample evidences for lateral transfer of azoreductase gene among enteric bacteria. There were also indications that azoreductase probably evolved in prokaryotes and then it was laterally transferred to eukaryotes in multiple events, resulting in some sequence variation among eukaryotic azoreductases. Finally, profile HMMs and conserved motifs extracted from these azoreductase sequences were found to provide sensitive tools for identifying potential azoreductases from the database. The analysis techniques used in this study can be extended to other gene trees to verify their evolutionary histories.