Featuring memory of past inputs is a fundamental requirement for machine learning models processing time-dependent data. In quantum reservoir computing, all architectures proposed so far rely on Markovian dynamics, which, as we prove, inherently lead to an exponential decay of past information, thereby limiting long-term memory capabilities. We demonstrate that non-Markovian dynamics can overcome this limitation, enabling extended memory retention. By analytically deriving memory bounds and supporting our findings with numerical simulations, we show that non-Markovian reservoirs can outperform their Markovian counterparts, particularly in tasks that require a coexistence of short- and long-term correlations. We introduce an embedding approach that allows a controlled transition from Markovian to non-Markovian evolution, providing a path for practical implementations. Our results establish quantum non-Markovianity as a key resource for enhancing memory in quantum machine learning architectures, with broad implications in quantum neural networks.