Dermatan sulfate (DS) accelerates the inhibition of thrombin by heparin cofactor II (HCII). A hexasaccharide consisting of three L-iduronic acid 2-O-sulfate (IdoA2SO3)→N-acetyl-D-galactosamine 4-O-sulfate (GalNAc4SO3) subunits was previously isolated from porcine skin DS and shown to bind HCII with high affinity. DS from porcine intestinal mucosa has a much lower content of this disaccharide but activates HCII with potency similar to that of porcine skin DS. Therefore, we sought to characterize oligosaccharides from porcine mucosal DS that interact with HCII. DS was partially depolymerized with chondroitinase ABC, and oligosaccharides containing 2–12 monosaccharide units were isolated. The oligosaccharides were then fractionated by anion-exchange and affinity chromatography on HCII-Sepharose, and the disaccharide compositions of selected fractions were determined. We found that the smallest oligosaccharides able to bind HCII were hexasaccharides. Oligosaccharides 6–12 units long that lacked uronic acid (UA)2SO3 but contained one or two GalNAc4,6SO3 residues bound, and binding was proportional to both oligosaccharide size and number of GalNAc4,6SO3 residues. Intact DS and bound dodecasaccharides contained predominantly IdoA but little D-glucuronic acid. Decasaccharides and dodecasaccharides containing one or two GalNAc4,6SO3 residues stimulated thrombin inhibition by HCII and prolonged the clotting time of normal but not HCII-depleted human plasma. These data support the hypothesis that modification of IdoA→GalNAc4SO3 subunits in the DS polymer by either 2-O-sulfation of IdoA or 6-O-sulfation of GalNAc can generate molecules with HCII-binding sites and anticoagulant activity.