The prokaryotic ubiquitin-like protein Pup targets substrates for degradation by the Mycobacterium tuberculosis proteasome through its interaction with Mpa, an ATPase that is thought to abut the 20S catalytic subunit. Ubiquitin, which is assembled into a polymer to similarly signal for proteasomal degradation in eukaryotes, adopts a stable and compact structural fold that is adapted into other proteins for diverse biological functions. We used NMR spectroscopy to demonstrate that, unlike ubiquitin, the 64-amino-acid protein Pup is intrinsically disordered with small helical propensity in the C-terminal region. We found that the Pup:Mpa interaction involves an extensive contact surface that spans S21-K61 and that the binding is in the "slow exchange" regime on the NMR time scale, thus demonstrating higher affinity than most ubiquitin:ubiquitin receptor pairs. Interestingly, during the titration experiment, intermediate Pup species were observable, suggesting the formation of one or more transient state(s) upon binding. Moreover, Mpa selected one configuration for a region undergoing chemical exchange in the free protein. These findings provide mechanistic insights into Pup's functional role as a degradation signal.