Cross-linking mass spectrometry has become an important approach for studying protein structures and protein-protein interactions. The amino acid compositions of some protein regions impede the detection of cross-linked residues, although it would yield invaluable information for protein modeling. Here, we report on a sequential-digestion strategy with trypsin and elastase to penetrate regions with a low density of trypsin-cleavage sites. We exploited intrinsic substrate-recognition properties of elastase to specifically target larger tryptic peptides. Our application of this protocol to the TAF4-12 complex allowed us to identify cross-links in previously inaccessible regions.