Quantum technologies rely on the ability to coherently transfer information encoded in quantum states along quantum channels. Decoherence induced by the environment sets limits on the efficiency of any quantum-enhanced protocol. Generally, the longer a quantum channel is the worse its capacity is. We show that for non-Markovian quantum channels this is not always true: surprisingly the capacity of a longer channel can be greater than of a shorter one. We introduce a general theoretical framework linking non-Markovianity to the capacities of quantum channels and demonstrate how harnessing non-Markovianity may improve the efficiency of quantum information processing and communication.