Phosphorylation of both small molecules and proteins plays a central role in many biological processes. In proteins, phosphorylation most commonly targets the oxygen atoms of Ser, Thr, and Tyr. In contrast, stably phosphorylated His residues are rarely found, due to the lability of the N-P bond, and histidine phosphorylation features most often in transient processes. Here we present the crystal structure of a protein of previously unknown function, which proves to contain a stably phosphorylated histidine residue. The protein is the product of open reading frame PAE2307, from the hyperthermophilic archaeon Pyrobaculum aerophilum, and is representative of a highly conserved protein family found in archaea and bacteria. The crystal structure of PAE2307, solved at 1.45-A resolution (R = 0.208, R(free) = 0.227), forms a remarkably tightly associated hexamer. The phosphorylated histidine at the proposed active site, pHis85, occupies a cavity that is at the interface between two subunits and contains a number of fully conserved residues. Stable phosphorylation is attributed to favorable hydrogen bonding of the phosphoryl group and a salt bridge with pHis85 that provides electronic stabilization. In silico modeling suggested that the protein may function as an adenosine kinase, a conclusion that is supported by in vitro assays of adenosine binding, using fluorescence spectroscopy, and crystallographic visualization of an adenosine complex of PAE2307 at 2.25-A resolution.