The structures of apo- and holorubredoxins from Pyrococcus furiosus (PfRd) and Clostridium pasteurianum (CpRd) have been investigated and compared using residual dipolar couplings to probe the origin of thermostability. In the native, metal (Fe or Zn) containing form, both proteins can maintain native structure at very high temperatures (>70 degrees C) for extended periods of time. Significant changes in either structure or backbone dynamics between 25 and 70 degrees C are not apparent for either protein. A kinetic difference with respect to metal loss is observed as in previous studies, but the extreme stability of both proteins in the presence of metal makes thermodynamic differences difficult to monitor. In the absence of metal, however, a largely reversible thermal denaturation can be monitored, and a comparison of the two apoproteins can offer insights into the origin of stability. Below denaturation temperatures apo-PfRd is found to have a structure nearly identical to that of the native holo form, except immediately adjacent to the metal binding site. In contrast, apo-CpRd is found to have a structure distinctly different from that of its holo form at low temperatures. This structure is rapidly lost upon heating, unfolding at approximately 40 degrees C. A PfRd mutant with the hydrophobic core mutated to match that of CpRd shows no change in thermostability in the metal-free state. A metal-free chimera with residues 1-15 of CpRd and the remaining 38 residues of PfRd is severely destabilized and is unfolded at 25 degrees C. Hence, the hydrophobic core does not seem to be the key determinant of thermostability; instead, data point to the hydrogen bond network centered on the first 15 residues or the interaction of these 15 residues with other parts of the protein as a possible contributor to the thermostability.