Abstract : Many quantum information tasks rely on entanglement, which is used as a resource, for example, to enable efficient and secure communication. Typically, noise, accompanied by loss of entanglement, reduces the efficiency of quantum protocols. Here we demonstrate experimentally a superdense coding scheme with noise, where the decrease of entanglement in Alice's encoding state does not reduce the efficiency of the information transmission. Having almost fully dephased classical two-photon polarization state at the time of encoding with concurrence 0.163, we reach values of mutual information close to 1.52 (1.89) with 3-state (4-state) encoding.This high efficiency relies both on non-Markovian features, that Bob exploits just before his Bell-state measurement, and on very high visibility (99.6%) of the Hong-Ou-Mandel interference within the experimental set-up. Our proof-of-principle results pave the way for exploiting non-Markovianity to improve the efficiency and security of quantum information processing tasks.