We consider a quantum relay that is used by two parties to perform several continuous-variable protocols of quantum communication, from entanglement distribution (swapping and distillation) to quantum teleportation, and quantum key distribution. The theory of these protocols is suitably extended to a non-Markovian model of decoherence characterized by correlated Gaussian noise in the bosonic environment. In the worst-case scenario where bipartite entanglement is completely lost at the relay, we show that the various protocols can be reactivated by the assistance of classical (separable) correlations in the environment. In fact, above a critical amount, these correlations are able to guarantee the distribution of a weaker form of entanglement (quadripartite), which can be localized by the relay into a stronger form (bipartite) that is exploitable by the parties. Our findings are confirmed by a proof-of-principle experiment where we show, for the first time, that memory effects in the environment can drastically enhance the performance of a quantum relay, well beyond the single-repeater bound for quantum and private communications.