The archaeosine tRNA-guanine transglycosylase from the hyperthermophilic archaeon Pyrococcus horikoshii was crystallized and preliminary X-ray characterization was performed. Single crystals were grown by the hanging-drop vapour-diffusion method, using sodium/potassium phosphate and sodium acetate as precipitants. The space group is P4(1)2(1)2 or P4(3)2(1)2, with unit-cell parameters a = b = 99.28 (14), c = 363.74 (56) A. The cryocooled crystals diffracted X-rays beyond 2.2 A resolution using synchrotron radiation from station BL44XU at SPring-8 (Harima). Selenomethionine-substituted protein crystals were prepared in order to solve the structure by the MAD phasing method.