Non-rigid structure-from-motion in an on-line setting holds many promises for useful applications, and off-line reconstruction techniques are already very advanced. Literature has only recently started focusing on on-line reconstruction, with only a handful of existing techniques available. Here we propose a novel method of history representation which utilizes the advances in off-line reconstruction. We represent the history as a set of keyframes, a representative subset of all past frames. This history representation is used as side-information in the estimation of individual frames. We expand the history as previously unseen frames arrive and compress it again when its size grows too large. We evaluate the proposed method on some test sequences, focusing on a human face in a conversation. While on-line algorithms can never perform as well as off-line methods as they have less information available, our method compares favourably to the state of the art off-line methods.