Histamine dehydrogenase (HADH) catalyzes the oxidative deamination of histamine, resulting in the production of imidazole acetaldehyde and an ammonium ion. The enzyme isolated from the newly identified halophilic archaeon Natrinema gari BCC 24369 is significantly different from the previously described protein from Nocardioides simplex. This newly identified HADH comprises three subunits with molecular weights of 49.0, 24.7 and 23.9 kDa, respectively, and is optimally active under high-salt conditions (3.5–5 M NaCl). As a step in the exploration of the unique properties of the protein, the HADH heterotrimer was purified and crystallized. Crystals were obtained using the sitting-drop vapor-diffusion method from a solution composed of 0.2 M calcium chloride dihydrate, 0.1 M HEPES pH 7.5, 28% PEG 400. Diffraction data were collected at −173°C to a resolution limit of 2.4 Å on the Southeast Regional Collaborative Access Team (SER-CAT) beamline 22-ID at the Advanced Photon Source, Argonne National Laboratory. The crystals belonged to the monoclinic space group C2, with unit-cell parameters a = 211.9, b = 58.6, c = 135.4 Å, β = 103.0°. The estimated Matthews coefficient is 3.21 Å3 Da−1, corresponding to 61.7% solvent content.