The three-dimensional structures of cystatins, and other evidence, suggest that the flexible N-terminal region of these inhibitors may bind to target proteinases independent of the two rigid hairpin loops forming the remainder of the inhibitory surface. In an attempt to demonstrate such two-step binding, which could not be identified in previous kinetics studies, we introduced a cysteine residue before the N-terminus of cystatin A and labeled this residue with fluorescent probes. Binding of AANS- and AEDANS-labeled cystatin A to papain resulted in ∼4-fold and 1.2-fold increases of probe fluorescence, respectively, reflecting the interaction of the N-terminal region with the enzyme. Observed pseudo-first-order rate constants, measured by the loss of papain activity in the presence of a fluorogenic substrate, for the reaction of the enzyme with excess AANS-cystatin A increased linearly with the concentration of the latter. In contrast, pseudo-first-order rate constants, obtained from measurements of the change of probe fluorescence with either excess enzyme or labeled inhibitor, showed an identical hyperbolic dependence on the concentration of the reactant in excess. This dependence demonstrates that the binding occurs in two steps, and implies that the labeled N-terminal region of cystatin A interacts with the proteinase in the second step, subsequent to the hairpin loops. The comparable affinities and dissociation rate constants for the binding of labeled and unlabeled cystatin A to papain indicate that the label did not appreciably perturb the interaction, and that unlabeled cystatin therefore also binds in a similar two-step manner. Such independent binding of the N-terminal regions of cystatins to target proteinases after the hairpin loops may be characteristic of most cystatin–proteinase reactions.