N-degron pathways are proteolytic systems that target proteins bearing N-terminal (Nt) degradation signals (degrons) called N-degrons. Nt-Arg of a protein is among Nt-residues that can be recognized as destabilizing ones by the Arg/N-degron pathway. A proteolytic cleavage of a protein can generate Arg at the N terminus of a resulting C-terminal (Ct) fragment either directly or after Nt-arginylation of that Ct-fragment by the Ate1 arginyl-tRNA-protein transferase (R-transferase), which uses Arg-tRNAArg as a cosubstrate. Ate1 can Nt-arginylate Nt-Asp, Nt-Glu, and oxidized Nt-Cys* (Cys-sulfinate or Cys-sulfonate) of proteins or short peptides. Ate1 genes of fungi, animals, and plants have been cloned decades ago, but a three-dimensional structure of Ate1 remained unknown. A detailed mechanism of arginylation is unknown as well. We describe here the crystal structure of the Ate1 R-transferase from the budding yeast Kluyveromyces lactis. The 58-kDa R-transferase comprises two domains that recognize, together, an acidic Nt-residue of an acceptor substrate, the Arg residue of Arg-tRNAArg, and a 3'-proximal segment of the tRNAArg moiety. The enzyme's active site is located, at least in part, between the two domains. In vitro and in vivo arginylation assays with site-directed Ate1 mutants that were suggested by structural results yielded inferences about specific binding sites of Ate1. We also analyzed the inhibition of Nt-arginylation activity of Ate1 by hemin (Fe3+-heme), and found that hemin induced the previously undescribed disulfide-mediated oligomerization of Ate1. Together, these results advance the understanding of R-transferase and the Arg/N-degron pathway.