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. We develop and 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 an almost fully dephased classical two-photon polarization state at the time of encoding with concurrence of , we reach values of mutual information close to $1.52\pm 0.02\(1.89\pm 0.05) $ 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 of the Hong-Ou-Mandel interference within the experimental set-up. Our proof-of-principle results with measurements on mutual information pave the way for exploiting non-Markovianity to improve the efficiency and security of quantum information processing tasks.