We investigate the impact on survival of a modification of the evolution of a sub-stochastic Markov chain that involves random relocations at previously visited states. Our central result is that such preferential relocations increase the persistence rate, meaning the survival probability decays more slowly than for the benchmark chain without relocations, and this improvement is strict under mild assumptions. We derive explicit lower bounds on the ratio of persistence rates when the relocation distribution is highly dispersed. The analysis relies on ergodic properties of so-called chains with complete connections, and a Feynman--Kac approach to estimate persistence.