Chemical cross-linking coupled to mass spectrometry provides structural information that is useful for probing protein conformations and providing experimental support for molecular models. "Zero-length" cross-links have greater value for these applications than longer cross-links because they provide more stringent distance constraints. However, this method is less commonly utilized because it cannot take advantage of isotopic labels, MS-labile bonds, or enrichment tags to facilitate identification. In this study, we combined label-free precursor ion quantitation and targeted tandem mass spectrometry with a new software tool, Zero-length Cross-link Miner (ZXMiner), to form a multitiered analysis strategy. A major, critical objective was to simultaneously achieve very high accuracy with essentially no false-positive cross-link identifications while maintaining a good depth of analysis. Our strategy was optimized on several proteins with known crystal structures. Comparison of ZXMiner to several existing cross-link analysis software showed that other algorithms detected less true positive cross-links and were far less accurate. Although prior use of zero-length cross-linking was typically restricted to small proteins, ZXMiner and the associated strategy enable facile analysis of very large protein complexes. This was demonstrated by identification of zero-length cross-links using purified 526 kDa spectrin heterodimers and intact red cell membranes and membrane skeletons.