Ubiquitin modification also occurs in archaea. Here, the authors characterize an archaeal ancestral ubiquitination system, present the crystal structure of the archaeal deubiquitinase Rpn11 from Caldiarchaeum subterraneum bound to ubiquitin and provide insights into evolutionary relationships.