Heparan sulfate is a highly sulfated polysaccharide abundantly present in the extracellular matrix. Heparan sulfate consists of a disaccharide repeating unit of glucosamine and glucuronic and iduronic acid residues. The functions of heparan sulfate are largely dictated by its size as well as the sulfation patterns. Heparanase is an enzyme that cleaves heparan sulfate polysaccharide into smaller fragments, regulating the functions of heparan sulfate. Understanding the substrate specificity plays a critical role in dissecting the biological functions of heparanase and heparan sulfate. The prevailing view is that heparanase recognizes specific sulfation patterns in heparan sulfate. However, emerging evidence suggests that heparanase is capable of varying its substrate specificities depending on the saccharide structures around the cleavage site. The plastic substrate specificity suggests a complex role of heparanase in regulating the structures of heparan sulfate in matrix biology.