The structure of two Thermotoga maritima proteins, a conserved hypothetical protein (TM0160) and a transcriptional regulator (TM1171), have now been determined at 1.9 A and 2.3 A resolution, respectively, as part of a large-scale structural genomics project. Our first efforts to crystallize full-length versions of these targets were unsuccessful. However, analysis of the recombinant purified proteins using the technique of enhanced amide hydrogen/deuterium exchange mass spectroscopy (DXMS) revealed substantial regions of rapid amide deuterium hydrogen exchange, consistent with flexible regions of the structures. Based on these exchange data, truncations were designed to selectively remove the disordered C-terminal regions, and the resulting daughter proteins showed greatly enhanced crystallizability. Comparative DXMS analysis of full-length protein versus truncated forms demonstrated complete and exact preservation of the exchange rate profiles in the retained sequence, indicative of conservation of the native folded structure. This study presents the first structures produced with the aid of the DXMS method for salvaging intractable crystallization targets. The structure of TM0160 represents a new fold and highlights the use of this approach where any prior structural knowledge is absent. The structure of TM1171 represents an example where the lack of a substrate/cofactor may impair crystallization. The details of both structures are presented and discussed.