A nonmonotonic, two-stage dewetting behavior was observed for spin coated thin viscoelastic polymer films on soft elastic substrates. At times shorter than the relaxation time of the polymer (t<tau_{rep}), dewetting generated deep trenches in the soft rubbery substrate which, in turn, almost stopped dewetting. At later stages (t>tau_{rep}), dewetting accelerated, accompanied by an unstable rim. However, holes nucleated at t<tau_{rep} showed only this second-stage behavior. Our observations are attributed to large elastic deformations in the substrate caused by transient residual stresses within the film.