We consider the behavior of random heteropolymers (RHP's) in random me
dia via Monte Carlo simulations. When the bare heteropolymer prefers u
nlike segments to be adjacent to each other, the disordered medium ind
uces rather unusual behavior. As temperature is scanned, we find two f
rozen phases with different ''folding'' patterns separated by a reentr
ant phase. The phenomena revealed by our results are elucidated on phy
sical grounds, experimental tests are suggested, and the agreement bet
ween the simulation results and a simple analytical calculation is dis
cussed.