We have studied the correlation between structural dynamics and function of the hairpin ribozyme. The enzyme-substrate complex exists in either docked (active) or undocked (inactive) conformations. Using single-molecule fluorescence methods, we found complex structural dynamics with four docked states of distinct stabilities and a strong memory effect where each molecule rarely switches between different docked states. We also found substrate cleavage to be rate-limited by a combination of conformational transitions and reversible chemistry equilibrium. The complex structural dynamics quantitatively explain the heterogeneous cleavage kinetics common to many catalytic RNAs. The intimate coupling of structural dynamics and function is likely a general phenomenon for RNA.