Bacterial ferredoxins are small iron-sulfur binding proteins that function as soluble electron shuttles between redox enzymes in the cell. Their simple 2x(β-α-β) fold, central metabolic function, and ubiquity across all kingdoms of life have led to the proposal that ferredoxins were likely among the earliest proteins. Today, ferredoxin-like folds are embedded in large, multidomain enzymes, suggesting ancient gene duplication and fusion events. In some cases, these embedded domains may have scant sequence or even structural homology to soluble counterparts, challenging the use of traditional phylogenetic tools to establish evolutionary relationships. In this study, we identify fragments of bacterial ferredoxins within larger oxidoreductases by integrating comparative sequence, structure, and dynamical attributes. Dynamics are computed using an elastic network model and analyzed for similarity of major normal modes. Using comparative dynamics, fragments of ferredoxin domains are found within larger proteins, even in cases of limited structural homology. This study also reveals a non-linear relationship between dynamical and structural similarities, suggesting that protein dynamics are more constrained than structure through evolutionary time. We propose that dynamical similarity is indicative of functional similarity. And, since nature selects for function, that the inclusion of dynamical similarity, in addition to sequence and structure similarities, provides a more robust framework for inferring homology. Inclusion of dynamical attributes in comparative analysis will lead to a greater understanding of the deep-time evolution of modern protein nanomachines.