In eukaryotes, the covalent attachment of ubiquitin chains directs substrates to the proteasome for degradation. Recently, ubiquitin-like modifications have also been described in the archaeal domain of life. It has subsequently been hypothesized that ubiquitin-like proteasomal degradation might also operate in these microbes, since all archaeal species utilize homologues of the eukaryotic proteasome. Here we perform a structural and biochemical analysis of a ubiquitin-like modification pathway in the archaeon Sulfolobus acidocaldarius. We reveal that this modifier is homologous to the eukaryotic ubiquitin-related modifier Urm1, considered to be a close evolutionary relative of the progenitor of all ubiquitin-like proteins. Furthermore we demonstrate that urmylated substrates are recognized and processed by the archaeal proteasome, by virtue of a direct interaction with the modifier. Thus, the regulation of protein stability by Urm1 and the proteasome in archaea is likely representative of an ancient pathway from which eukaryotic ubiquitin-mediated proteolysis has evolved.