We present an analytical theory for heteropolymer deformation, as exemplified experimentally by stretching of single protein molecules. Using a mean-field replica theory, we determine phase diagrams for stress-induced unfolding of typical random sequences. This transition is sharp in the limit of infinitely long chain molecules. But for chain lengths relevant to biological macromolecules, partially unfolded conformations prevail over an intermediate range of stress. These necklace-like structures, comprised of alternating compact and extended subunits, are stabilized by quenched variations in the composition of finite chain segments. The most stable arrangements of these subunits are largely determined by preferential extension of segments rich in solvophilic monomers. This predicted significance of necklace structures explains recent observations in protein stretching experiments. We examine the statistical features of select sequences that give rise to mechanical strength and may thus have guided the evolution of proteins that carry out mechanical functions in living cells.

10 pages, 6 figures