We present the first atomic model of a substrate-bound inner mitochondrial membrane AAA+ quality control protease, YME1. Our ~3.4 Å cryo-EM structure reveals how the ATPases form a closed spiral staircase encircling an unfolded substrate, directing it toward the flat, symmetric protease ring. Importantly, the structure reveals how three coexisting nucleotide states allosterically induce distinct positioning of tyrosines in the central channel, resulting in substrate engagement and translocation to the negatively charged proteolytic chamber. This tight coordination by a network of conserved residues defines a sequential, around-the-ring ATP hydrolysis cycle that results in step-wise substrate translocation. Furthermore, we identify a hinge-like linker that accommodates the large-scale nucleotide-driven motions of the ATPase spiral independently of the contiguous planar proteolytic base. These results define the first molecular mechanism for a mitochondrial inner membrane AAA+ protease and reveal a translocation mechanism likely conserved for other AAA+ ATPases.