How small can a free-living organism be? On the surface, this question is straightforward-in principle, the smallest cells can be identified and measured. But understanding what factors determine this lower limit, and addressing the host of other questions that follow on from this knowledge, require a fundamental understanding of the chemistry and ecology of cellular life. The recent report of evidence for life in a martian meteorite and the prospect of searching for biological signatures in intelligently chosen samples from Mars and elsewhere bring a new immediacy to such questions. How do we recognize the morphological or chemical remnants of life in rocks deposited 4 billion years ago on another planet? Are the empirical limits on cell size identified by observation on Earth applicable to life wherever it may occur, or is minimum size a function of the particular chemistry of an individual planetary surface? These questions formed the focus of a workshop on the size limits of very small organisms, organized by the Steering .Group for the Workshop on Size Limits of Very Small Microorganisms and held on October 22 and 23, 1998. Eighteen invited panelists, representing fields ranging from cell biology and molecular genetics to paleontology and mineralogy, joined with an almost equal number of other participants in a wide-ranging exploration of minimum cell size and the challenge of interpreting micro- and nano-scale features of sedimentary rocks found on Earth or elsewhere in the solar system. This document contains the proceedings of that workshop. It includes position papers presented by the individual panelists, arranged by panel, along with a summary, for each of the four sessions, of extensive roundtable discussions that involved the panelists as well as other workshop participants.