The glycosaminoglycan heparin is known to possess antimetastatic activity in experimental models and preclinical studies, but there is still uncertainty over its mechanism of action in this respect. As an anticoagulant, heparin enhances inhibition of thrombin by the serpin antithrombin III, but a similar cofactor role has not been previously investigated for proteases linked to metastasis. The squamous cell carcinoma antigens (serpins B3 and B4) are tumor-associated proteins that can inhibit papain-like cysteine proteases, including cathepsins L, K, and S. In this study, we show that SCCA-1 (B3) and SCCA-2 (B4) can bind heparin as demonstrated by affinity chromatography, native PAGE gel shifts, and intrinsic fluorescence quenching. Binding was specific for heparin and heparan sulfate but not other glycosaminoglycans. The presence of heparin accelerated inhibition of cathepsin L by both serpins, and in the case of SCCA-1, heparin increased the second order inhibition rate constant from 5.4 × 105 to >108, indicating a rate enhancement of at least 180-fold. A templating mechanism was shown, consistent with ternary complex formation. Furthermore, SCCA-1 inhibition of cathepsin L-like proteolytic activity secreted from breast and melanoma cancer cell lines was significantly enhanced by heparin. This is the first example of glycosaminoglycan enhancement of B-clade serpin activity and the first report of heparin acting as a cofactor in serpin cross-class inhibition of cysteine proteases. Most importantly, this finding raises the possibility that the anticancer properties of heparin may be due, at least partly, to enhanced inhibition of prometastatic proteases.