We present an experiment demonstrating entanglement-enhanced classical communication capacity of a quantum channel with correlated noise. The channel is modelled by a fiber optic link exhibiting random birefringence that fluctuates on a time scale much longer than the temporal separation between consecutive uses of the channel. In this setting, introducing entanglement between two photons travelling down the fiber allows one to encode reliably up to one bit of information into their joint polarization degree of freedom. When no quantum correlations between two separate uses of the channel are allowed, this capacity is reduced by a factor of more than three. We demonstrated this effect using a fiber-coupled source of entagled photon pairs based on spontaneous parametric down-conversion, and a linear-optics Bell state measurement.