The Cdc48 adenosine triphosphatase (ATPase) (p97 or valosin-containing protein in mammals) and its cofactor Ufd1/Npl4 extract polyubiquitinated proteins from membranes or macromolecular complexes for subsequent degradation by the proteasome. How Cdc48 processes its diverse and often well-folded substrates is unclear. Here, we report cryo-electron microscopy structures of the Cdc48 ATPase in complex with Ufd1/Npl4 and polyubiquitinated substrate. The structures show that the Cdc48 complex initiates substrate processing by unfolding a ubiquitin molecule. The unfolded ubiquitin molecule binds to Npl4 and projects its N-terminal segment through both hexameric ATPase rings. Pore loops of the second ring form a staircase that acts as a conveyer belt to move the polypeptide through the central pore. Inducing the unfolding of ubiquitin allows the Cdc48 ATPase complex to process a broad range of substrates.