I think, the first mark‑and‑sweep collector was published in McCarthy's 1960 Communications of the ACM paper "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". It's resonable to assume, that they already had it when Steve Russell implemented the first Lisp evaluator, but we don't know exactly when it was added.