How biological machines harness ATP to drive mechanical work remains a crucial question. Structural studies of protein-translocating AAA+ machines proposed a coupled and sequential translocation process, whereby ATP hydrolysis events lead to short threading steps. Yet, direct real-time observation of these events remains elusive. Here, we employ single-molecule FRET spectroscopy to track substrate translocation through ClpB, a quality control AAA+ machine. We isolate ClpB and its substrate within lipid vesicles and find that translocation events, while dependent on ATP, take milliseconds, much faster than ATP hydrolysis times. Surprisingly, the translocation rate depends weakly on temperature and ATP concentration. Using three-color FRET experiments, we find that translocation events can occur bidirectionally but are not always complete. Replacing ATP with the slowly hydrolysable analog ATP{gamma}S abolishes both rapid translocation and directionality. These results indicate a fast, stochastic Brownian-motor-like mechanism, redefining how ATP is coupled with mechanical action in AAA+ machines.