第一種實用和完善的垃圾收集算法是 J. McCarthy 等人在 1960 年提出并成功地應用于 Lisp 語言的標記－清除算法。仍以餐巾紙為例，標記－清除算法的執行過程是這樣的：
午餐過程中，餐廳里的所有人都根據自己的需要取用餐巾紙。當垃圾收集機器人想收集廢舊餐巾紙的時候，它會讓所有用餐的人先停下來，然后，依次詢問餐廳里的每一個人：“你正在用餐巾紙嗎？你用的是哪一張餐巾紙？”機器人根據每個人的回答將人們正在使用的餐巾紙畫上記號。詢問過程結束后，機器人在餐廳里尋找所有散落在餐桌上且沒有記號的餐巾紙（這些顯然都是用過的廢舊餐巾紙），把它們統統扔到垃圾箱里。
正如其名稱所暗示的那樣，標記－清除算法的執行過程分為“標記”和“清除”兩大階段。這種分步執行的思路奠定了現代垃圾收集算法的思想基礎。與引用計數算法不同的是，標記－清除算法不需要運行環境監測每一次內存分配和指針操作，而只要在“標記”階段中跟蹤每一個指針變量的指向——用類似思路實現的垃圾收集器也常被后人統稱為跟蹤收集器（ Tracing Collector ）
伴隨著 Lisp 語言的成功，標記－清除算法也在大多數早期的 Lisp 運行環境中大放異彩。盡管最初版本的標記－清除算法在今天看來還存在效率不高（標記和清除是兩個相當耗時的過程）等諸多缺陷，但在后面的討論中，我們可以看到，幾乎所有現代垃圾收集算法都是標記－清除思想的延續，僅此一點， J. McCarthy 等人在垃圾收集技術方面的貢獻就絲毫不亞于他們在 Lisp 語言上的成就了。