Quantum technologies require states with high purity—or, in thermodynamic terms, low temperatures. Given finite resources, the Third Law of thermodynamics prohibits perfect cooling; nonetheless, the ultimate cooling limits for a system interacting with quantum machines have been derived for the memoryless (Markovian) setting, where each refrigeration step proceeds independently of those previous. Here, we incorporate memory via a generalized collision model to analyze its role in quantum cooling. We demonstrate exponential enhancement over the memoryless case and derive the optimal protocol. For qubits, our limit coincides with that of heat-bath algorithmic cooling, which our framework generalizes to arbitrary dimensions.