We propose a new matching algorithm—Unpaired kidney exchange—to tackle the problem of double coincidence of wants without using money. The fundamental idea is that “memory” can serve as a medium of exchange. In a dynamic matching model with heterogeneous agents, we prove that average waiting time under the Unpaired algorithm is close-to optimal, and substantially less than the standard pairwise and chain exchange algorithms. We evaluate this algorithm using a rich dataset of the kidney patients in France. Counterfactual simulations show that the Unpaired algorithm can match nearly 57% of the patients, with an average waiting time of 424 days (state-of-the-art algorithms match about 31% with an average waiting time of 675 days or more). The optimal algorithm performs only slightly better: it matches 58% of the patients and leads to an average waiting time of 410 days. The Unpaired algorithm confronts two incentive-related practical challenges. We address those challenges via a practical version of the Unpaired algorithm that employs kidneys from the deceased donors waiting list. The practical version can match nearly 87% of patient-donor pairs, while reducing the average waiting time to about 141 days.