We present an analytical theory for heteropolymer deformation, as exemplified experimentally by stretching of single protein molecules. Using replica mean-field 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. However, for chain lengths relevant to biological macromolecules, partially unfolded conformations prevail over an intermediate range of stress. These necklacelike 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.